代码

#include <bits/stdc++.h>
#include <immintrin.h>
#pragma GCC target("avx512f")

using namespace std;
using uint = unsigned int;
using ull = unsigned long long;

int read() {
    const int M = 1e6;
    static streambuf* in = cin.rdbuf();
    #define gc (p1 == p2 && (p2 = (p1 = buf) + in -> sgetn(buf, M), p1 == p2) ? -1 : *p1++)
    static char buf[M], *p1, *p2;
    int c = gc;
    while(c < 48) c = gc;
    return c & 15;
}
void wrt(int x) {
    static streambuf* out = cout.rdbuf();
    #define pc out -> sputc
    static char c[11]; int sz = 0;
    do c[++sz] = x % 10, x /= 10; while(x);
    while(sz) pc(c[sz--] + 48);
    pc(32);
}

const uint M = 998244353;

int n, m, lim = 16, rev[1 << 18];
uint w[1 << 18];
__m512i a[1 << 14], b[1 << 14];

const auto A = (uint*)a, B = (uint*)b;

uint Pow(uint a, int n, uint r = 1) {
    for(; n; n >>= 1, a = (ull)a * a % M)
    if(n & 1) r = (ull)r * a % M;
    return r;
}
void NTT(__m512i a[], int t) {
    const auto _M = _mm512_set1_epi32(M);
    auto A = (uint*)a;
    for(int i = 0; i < lim; i++) if(rev[i] < i) swap(A[i], A[rev[i]]);
    uint tmp, x, y;
    for(int j = 0; j < lim; j += 2) {
        x = A[j + 0], tmp = y = (ull)A[j + 1] * w[1] % M;
        y = x - y, x += tmp;
        A[j + 0] = x < M ? x : x - M, A[j + 1] = y < M ? y : y + M;
    }
    for(int j = 0; j < lim; j += 4) {
        x = A[j + 0], tmp = y = (ull)A[j + 2] * w[2] % M;
        y = x - y, x += tmp;
        A[j + 0] = x < M ? x : x - M, A[j + 2] = y < M ? y : y + M;
        x = A[j + 1], tmp = y = (ull)A[j + 3] * w[3] % M;
        y = x - y, x += tmp;
        A[j + 1] = x < M ? x : x - M, A[j + 3] = y < M ? y : y + M;
    }
    for(int j = 0; j < lim; j += 8) {
        x = A[j + 0], tmp = y = (ull)A[j + 4] * w[4] % M;
        y = x - y, x += tmp;
        A[j + 0] = x < M ? x : x - M, A[j + 4] = y < M ? y : y + M;
        x = A[j + 1], tmp = y = (ull)A[j + 5] * w[5] % M;
        y = x - y, x += tmp;
        A[j + 1] = x < M ? x : x - M, A[j + 5] = y < M ? y : y + M;
        x = A[j + 2], tmp = y = (ull)A[j + 6] * w[6] % M;
        y = x - y, x += tmp;
        A[j + 2] = x < M ? x : x - M, A[j + 6] = y < M ? y : y + M;
        x = A[j + 3], tmp = y = (ull)A[j + 7] * w[7] % M;
        y = x - y, x += tmp;
        A[j + 3] = x < M ? x : x - M, A[j + 7] = y < M ? y : y + M;
    }
    for(int j = 0; j < lim; j += 16) {
        x = A[j + 0], tmp = y = (ull)A[j + 8] * w[8] % M;
        y = x - y, x += tmp;
        A[j + 0] = x < M ? x : x - M, A[j + 8] = y < M ? y : y + M;
        x = A[j + 1], tmp = y = (ull)A[j + 9] * w[9] % M;
        y = x - y, x += tmp;
        A[j + 1] = x < M ? x : x - M, A[j + 9] = y < M ? y : y + M;
        x = A[j + 2], tmp = y = (ull)A[j + 10] * w[10] % M;
        y = x - y, x += tmp;
        A[j + 2] = x < M ? x : x - M, A[j + 10] = y < M ? y : y + M;
        x = A[j + 3], tmp = y = (ull)A[j + 11] * w[11] % M;
        y = x - y, x += tmp;
        A[j + 3] = x < M ? x : x - M, A[j + 11] = y < M ? y : y + M;
        x = A[j + 4], tmp = y = (ull)A[j + 12] * w[12] % M;
        y = x - y, x += tmp;
        A[j + 4] = x < M ? x : x - M, A[j + 12] = y < M ? y : y + M;
        x = A[j + 5], tmp = y = (ull)A[j + 13] * w[13] % M;
        y = x - y, x += tmp;
        A[j + 5] = x < M ? x : x - M, A[j + 13] = y < M ? y : y + M;
        x = A[j + 6], tmp = y = (ull)A[j + 14] * w[14] % M;
        y = x - y, x += tmp;
        A[j + 6] = x < M ? x : x - M, A[j + 14] = y < M ? y : y + M;
        x = A[j + 7], tmp = y = (ull)A[j + 15] * w[15] % M;
        y = x - y, x += tmp;
        A[j + 7] = x < M ? x : x - M, A[j + 15] = y < M ? y : y + M;
    }
    lim >>= 4;
    for(int i = 1; i < lim; i <<= 1) {
        for(int j = i; j < lim; j += i << 1)
            for(int k = 0; k < i; k++) {
                uint *y = (uint*)(a + j + k), *z = w + (i + k << 4);
                #define Mul(i) y[i] = (ull)y[i] * z[i] % M
                Mul(0), Mul(1), Mul(2), Mul(3), Mul(4), Mul(5), Mul(6), Mul(7);
                Mul(8), Mul(9), Mul(10), Mul(11), Mul(12), Mul(13), Mul(14), Mul(15);
            }
        for(int j = 0; j < lim; j += i << 1)
            for(int k = j; k < j + i; k++) {
                __m512i &x = a[k], &y = a[k + i], t = y;
                #define Min _mm512_min_epu32
                #define Add _mm512_add_epi32
                #define Sub _mm512_sub_epi32
                y = Sub(x, y), y = Min(y, Add(y, _M));
                x = Add(x, t), x = Min(x, Sub(x, _M));
            }
    }
    lim <<= 4;
    if(t) reverse(A + 1, A + lim);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i <= n; i++) A[i] = read();
    for(int i = 0; i <= m; i++) B[i] = read();
    while(lim <= n + m) lim <<= 1;
    for(int i = 0; i < lim; i++) rev[i] = rev[i >> 1] >> 1 | (i & 1 ? lim >> 1 : 0);
    for(int i = 1; i < lim; i <<= 1) {
        ull wn = Pow(3, M / 2 / i);
        for(int j = 0; j < i; j++) w[i + j] = j ? w[i + j - 1] * wn % M : 1;
    }
    NTT(a, 0), NTT(b, 0);
    for(int i = 0; i < lim; i++) A[i] = (ull)A[i] * B[i] % M;
    NTT(a, 1);
    ull inv = Pow(lim, M - 2);
    for(int i = 0; i <= n + m; i++) wrt(A[i] * inv % M);
}

评测结果