代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 4e6 + 5;
struct buf {
    char a[1 << 25], *s;
    char b[1 << 25], *t;
    buf() : s(a), t(b) { a[fread(a, 1, sizeof a, stdin)] = 0; }
    ~buf() { fwrite(b, 1, t - b, stdout); }
    operator unsigned long long() {
        unsigned long long x = 0;
        while (*s < 48) ++s;
        while (*s > 32) x = x * 10 + *s++ - 48;
        return x;
    }
    void out(int x) {
        static char c[12];
        char *i = c;
        if (!x) {
            *t++ = 48;
        } else {
            while (x) {
                int y = x / 10;
                *i++ = x - y * 10 + 48, x = y;
            }
            while (i != c) *t++ = *--i;
        }
        *t++ = 32;
    }
} it;
namespace {  // radix_2_ntt
typedef unsigned long long valueType;
const valueType P = 998244353, G = 3;
valueType qpow(valueType x, valueType y) {
    valueType res = 1;
    for (; y; y >>= 1, x = x * x % P) {
        if (y & 1)
            res = res * x % P;
    }
    return res;
}
valueType inv(valueType x) { return qpow(x, P - 2); }
const valueType IMAG = P - qpow(G, P - 1 >> 2);
valueType EPS[N], INV[N];
void init(int n) {
    valueType g = qpow(G, (P - 1) / n);
    int l = n >> 1;
    EPS[l] /* = INV[1] */ = 1;
    for (int i = l + 1; i < n; ++i) EPS[i] = EPS[i - 1] * g % P;
    for (int i = l - 1; i > 0; --i) EPS[i] = EPS[i << 1];
    /* for (int i = 2; i < l; ++i) INV[i] = (P - P / i) * INV[P % i] % P; */
}
void revbin(int n, valueType x[]) {
    for (int i = 0, j = 0; i < n; ++i) {
        if (i < j)
            std::swap(x[i], x[j]);
        for (int k = n >> 1; (j ^= k) < k; k >>= 1) {
        }
    }
}
void dif_fft_core(int n, valueType x[]) {
    for (int i = n; i >= 2; i >>= 1)
        for (int j = 0, l = i >> 1; j < n; j += i)
            for (int k = 0; k < l; ++k) {
                valueType u = x[j + k], v = x[j + k + l];
                x[j + k] = (u + v) % P, x[j + k + l] = (u + P - v) * EPS[l + k] % P;
            }
}
void dit_fft_core(int n, valueType x[]) {
    for (int i = 2; i <= n; i <<= 1)
        for (int j = 0, l = i >> 1; j < n; j += i)
            for (int k = 0; k < l; ++k) {
                valueType u = x[j + k], v = EPS[l + k] * x[j + k + l] % P;
                x[j + k] = (u + v) % P, x[j + k + l] = (u + P - v) % P;
            }
}
void dft(int n, valueType x[]) { dif_fft_core(n, x); }
void idft(int n, valueType x[]) {
    dit_fft_core(n, x), std::reverse(x + 1, x + n);
    valueType in = P - (P - 1) / n;
    for (int i = 0; i < n; ++i) x[i] = x[i] * in % P;
}
/*
void derivative(int n, const valueType x[], valueType y[]) {
    for (int i = 1; i < n; ++i) y[i - 1] = x[i] * i % P;
    y[n - 1] = 0;
}
void integral(int n, const valueType x[], valueType y[]) {
    for (int i = n - 1; i; --i) y[i] = x[i - 1] * INV[i] % P;
    y[0] = 0;
}
void polyInv(int n, const valueType x[], valueType y[]) {
    assert(x != y && x[0] != 0);
    static valueType x_copy[N];
    memset(y, 0, sizeof(valueType) * (n << 1));
    y[0] = inv(x[0]);
    for (int i = 2; i <= n; i <<= 1) {
        int l = i << 1;
        memcpy(x_copy, x, sizeof(valueType) * i);
        memset(x_copy + i, 0, sizeof(valueType) * i);
        dft(l, x_copy), dft(l, y);
        for (int j = 0; j < l; ++j) y[j] = y[j] * (2 + P - (x_copy[j] * y[j]) % P) % P;
        idft(l, y);
        memset(y + i, 0, sizeof(valueType) * i);
    }
}
void polyLn(int n, const valueType x[], valueType y[]) {
    assert(x != y && x[0] == 1);
    static valueType dx[N];
    derivative(n, x, dx);
    memset(dx + n, 0, sizeof(valueType) * n);
    polyInv(n, x, y);
    int l = n << 1;
    dft(l, dx), dft(l, y);
    for (int i = 0; i < l; ++i) y[i] = dx[i] * y[i] % P;
    idft(l, y);
    integral(n, y, y);
    memset(y + n, 0, sizeof(valueType) * n);
}
void polyExp(int n, const valueType x[], valueType y[]) {
    assert(x != y && x[0] == 0);
    static valueType ln_y[N];
    memset(y, 0, sizeof(valueType) * (n << 1));
    y[0] = 1;
    for (int i = 2; i <= n; i <<= 1) {
        int l = i << 1;
        polyLn(i, y, ln_y);
        for (int j = ln_y[0] = 1; j < i; ++j) ln_y[j] = (x[j] + P - ln_y[j]) % P;
        dft(l, y), dft(l, ln_y);
        for (int j = 0; j < l; ++j) y[j] = y[j] * ln_y[j] % P;
        idft(l, y);
        memset(y + i, 0, sizeof(valueType) * i);
    }
}
void polySin(int n, const valueType x[], valueType y[]) {
    static valueType exp_ix[N], exp_neg_ix[N], ix[N];
    for (int i = 0; i < n; ++i) ix[i] = x[i] * IMAG % P;
    polyExp(n, ix, exp_ix), polyInv(n, exp_ix, exp_neg_ix);
    valueType iv = (P - (P - 1 >> 1)) * (P - IMAG) % P;
    for (int i = 0; i < n; ++i) y[i] = (exp_ix[i] + P - exp_neg_ix[i]) * iv % P;
}
void polyCos(int n, const valueType x[], valueType y[]) {
    static valueType exp_ix[N], exp_neg_ix[N], ix[N];
    for (int i = 0; i < n; ++i) ix[i] = x[i] * IMAG % P;
    polyExp(n, ix, exp_ix), polyInv(n, exp_ix, exp_neg_ix);
    valueType iv = P - (P - 1 >> 1);
    for (int i = 0; i < n; ++i) y[i] = (exp_ix[i] + exp_neg_ix[i]) * iv % P;
}
*/
};  // namespace
ull a[N], b[N];
int main() {
#ifdef LOCAL
    freopen("..\\in", "r", stdin), freopen("..\\out", "w", stdout);
#endif
    int n = it, m = it;
    for (int i = 0; i <= n; ++i) a[i] = it;
    for (int i = 0; i <= m; ++i) b[i] = it;
    int len = 1;
    while (len < n + m + 2) len <<= 1;
    init(len);
    dft(len, a), dft(len, b);
    for (int i = 0; i < len; ++i) (a[i] *= b[i]) %= P;
    idft(len, a);
    for (int i = 0; i <= n + m; ++i) it.out(static_cast<int>(a[i]));
    return 0;
}

评测结果