代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long llt;

const int MaxN = 4000000 + 5;
const llt g = 3;
const llt Mod = 998244353;

int N, M, V;
llt A[MaxN], B[MaxN], C[MaxN]; int R[MaxN];

inline llt Fast_pow(llt low, llt high) {
    llt res = 1;
    while (high) {
        if (high & 1) res = res * low % Mod;
        high >>= 1;
        low = low * low % Mod;
    }
    return res;
}

void init() {
    scanf("%d %d", &N, &M);
    N++; M++;
    for (int i = 0; i < N; ++i) scanf("%lld", &A[i]);
    for (int i = 0; i < M; ++i) scanf("%lld", &B[i]);
}

inline void NTT(llt a[], int n, llt f) {
    for (int i = 0; i < n; ++i)
        if (i < R[i]) swap(a[i], a[R[i]]);
    for (int i = 1; i < n; i <<= 1) {
        llt w = Fast_pow(Fast_pow(g, f), (Mod - 1) / (i << 1));
        for (int j = 0; j < n; j += (i << 1)) {
            llt x = 1;
            for (int k = 0; k < i; ++k, x = x * w % Mod) {
                llt lson = a[j + k], rson = a[i + j + k];
                a[j + k] = lson + rson * x;
                a[j + k] %= Mod;
                a[i + j + k] = lson - rson * x;
                a[i + j + k] %= Mod;
            }
        }
    }

    if (f == Mod - 2)
        for (int i = 0; i < n; ++i)
            a[i] = a[i] * Fast_pow(n, Mod - 2) % Mod;
}

void solve() {
    V = 1;
    while (V < N + M - 1) V <<= 1;
    for (int i = 1; i < V; ++i) {
        R[i] = (R[i >> 1] >> 1);
        if (i & 1) R[i] |= (V >> 1);
    }
    NTT(A, V, 1); NTT(B, V, 1);
    for (int i = 0; i < V; ++i)
        C[i] = A[i] * B[i] % Mod;
    NTT(C, V, Mod - 2);
    for (int i = 0; i < N + M - 1; ++i)
        printf("%lld ", (C[i] + Mod) % Mod);
    puts("");
}

int main() {
    init();
    solve();
    return 0;
}

评测结果