代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 4e6 + 5;
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, m;
    cin >> n >> m;
    for (int i = 0; i <= n; ++i) cin >> a[i];
    for (int i = 0; i <= m; ++i) cin >> b[i];
    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) cout << static_cast<int>(a[i]) << ' ';
    return 0;
}

评测结果