代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 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 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); }
valueType legendre_symbol(valueType x) {
    if (x == 0) return 0;
    return qpow(x, P - 1 >> 1) == 1 ? 1 : -1;
}
valueType tonelli_shanks(valueType a) {
    if (legendre_symbol(a) != 1) return 0;
    valueType q = P - 1, t = 0, n, z; // P = q * 2 ^ t + 1
    while (!(q & 1)) q >>= 1, ++t;
    if (t == 1) return qpow(a, P + 1 >> 2);
    for (n = 1; n < P; ++n) {
        if (legendre_symbol(n) == -1) {
            z = qpow(n, q);
            break;
        }
    }
    valueType y = z, r = t, x = qpow(a, q - 1 >> 1), b = x;
    x = x * a % P, b = x * b % P;
    while (1) {
        if (b == 1) return x;
        valueType m;
        for (m = 1; m < r; ++m) {
            if (qpow(b, (1LL << m) % P) == 1) break;
        }
        valueType v = qpow(y, (1LL << r - m - 1) % P);
        y = v * v % P, r = m, x = x * v % P, b = b * y % P;
    }
}
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 - 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];
                x[j + k] = (u + v) % P, x[j + k + l] = (u - 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] + P) * 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 - 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] - 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);
    }
}
valueType quadraticResiduesModP(valueType x) { return tonelli_shanks(x); }
void polySqrt(int n, const valueType x[], valueType y[]) {
    assert(x != y);
    static valueType x_copy[N], y_inv[N];
    memset(y, 0, sizeof(valueType) * (n << 1));
    assert((y[0] = quadraticResiduesModP(x[0])) != 0);
    if (P - y[0] < y[0]) y[0] = P - y[0];
    valueType inv2 = (P >> 1) + 1;
    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);
        polyInv(i, y, y_inv), dft(l, x_copy), dft(l, y), dft(l, y_inv);
        for (int j = 0; j < l; ++j) y[j] = inv2 * (y[j] + y_inv[j] * x_copy[j] % P) % P;
        idft(l, y);
        memset(y + i, 0, sizeof(valueType) * i);
    }
}
const valueType IMAG = P - qpow(G, P - 1 >> 2);
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] = (P + exp_ix[i] - 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
ll 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;
}

评测结果