代码

// v3: DIF forward + DIT inverse (no bitrev), precomputed twiddles, digit IO
#include <cstdio>
#include <cstring>
#include <cstdlib>

typedef unsigned long long u64;
typedef long long i64;

const int MOD = 998244353;
const int G = 3;
const int MAXN = 1 << 18;

static int a[MAXN], b[MAXN];
static int roots[MAXN];      // forward roots: G^((MOD-1)/n * k)
static int roots_inv[MAXN];  // inverse roots: G^{-(MOD-1)/n * k}

static inline int modpow(int base, i64 e) {
    i64 r = 1, bb = base % MOD;
    for (; e; e >>= 1) {
        if (e & 1) r = r * bb % MOD;
        bb = bb * bb % MOD;
    }
    return (int)r;
}

// forward DIF, output in bit-reversed order
static inline void ntt_fwd(int *x, int n, const int *rts) {
    for (int len = n; len > 1; len >>= 1) {
        int half = len >> 1;
        int step = n / len;
        for (int i = 0; i < n; i += len) {
            int *y = x + i;
            for (int j = 0; j < half; j++) {
                int u = y[j];
                int v = y[j + half];
                int s = u + v; if (s >= MOD) s -= MOD;
                int d = u - v; if (d < 0) d += MOD;
                y[j] = s;
                y[j + half] = (int)((i64)d * rts[j * step] % MOD);
            }
        }
    }
}

// inverse DIT, input in bit-reversed order
static inline void ntt_inv(int *x, int n, const int *rts) {
    for (int len = 2; len <= n; len <<= 1) {
        int half = len >> 1;
        int step = n / len;
        for (int i = 0; i < n; i += len) {
            int *y = x + i;
            for (int j = 0; j < half; j++) {
                int u = y[j];
                int v = (int)((i64)y[j + half] * rts[j * step] % MOD);
                int s = u + v; if (s >= MOD) s -= MOD;
                int d = u - v; if (d < 0) d += MOD;
                y[j] = s;
                y[j + half] = d;
            }
        }
    }
}

// fast input buffer
static const int BUFSZ = 1 << 20;
static char inbuf[BUFSZ];
static size_t inpos = 0, inlen = 0;

static inline int readbyte() {
    if (inpos >= inlen) {
        inlen = fread(inbuf, 1, BUFSZ, stdin);
        inpos = 0;
        if (inlen == 0) return -1;
    }
    return (unsigned char)inbuf[inpos++];
}

static inline int readint() {
    int c = readbyte();
    while (c == ' ' || c == '\n' || c == '\r' || c == '\t') c = readbyte();
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = readbyte();
    }
    return x;
}

// fast output buffer
static char outbuf[1 << 21];
static size_t outpos = 0;

static inline void putc(char c) { outbuf[outpos++] = c; }

static inline void putint(int x) {
    if (x == 0) { putc('0'); return; }
    char tmp[12]; int t = 0;
    while (x) { tmp[t++] = '0' + (x % 10); x /= 10; }
    while (t) putc(tmp[--t]);
}

int main() {
    int n = readint();
    int m = readint();
    int na = n + 1;
    int nb = m + 1;
    for (int i = 0; i < na; i++) a[i] = readint();
    for (int i = 0; i < nb; i++) b[i] = readint();

    int size = 1;
    while (size < na + nb - 1) size <<= 1;

    int wstep = (MOD - 1) / size;
    int w = modpow(G, wstep);
    int invw = modpow(w, MOD - 2);
    i64 cur = 1;
    for (int i = 0; i < size; i++) { roots[i] = (int)cur; cur = cur * w % MOD; }
    cur = 1;
    for (int i = 0; i < size; i++) { roots_inv[i] = (int)cur; cur = cur * invw % MOD; }

    ntt_fwd(a, size, roots);
    ntt_fwd(b, size, roots);
    for (int i = 0; i < size; i++) a[i] = (int)((i64)a[i] * b[i] % MOD);
    ntt_inv(a, size, roots_inv);

    int ninv = modpow(size, MOD - 2);
    for (int i = 0; i < size; i++) a[i] = (int)((i64)a[i] * ninv % MOD);

    int outn = n + m + 1;
    for (int i = 0; i < outn; i++) {
        if (i) putc(' ');
        putint(a[i]);
    }
    putc('\n');
    fwrite(outbuf, 1, outpos, stdout);
    return 0;
}

评测结果