代码

// v6: v3 with unsigned types + pragma optimize, branchless modmul via unsigned %
#pragma GCC optimize("O3,unroll-loops")
#include <cstdio>
#include <cstring>
#include <cstdlib>

typedef unsigned long long u64;
typedef unsigned int u32;
typedef long long i64;

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

static u32 a[MAXN], b[MAXN];
static u32 roots[MAXN];
static u32 roots_inv[MAXN];

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

// forward DIF (input natural, output bit-reversed)
static inline void ntt_fwd(u32 *x, int n, const u32 *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) {
            u32 *y = x + i;
            for (int j = 0; j < half; j++) {
                u32 u = y[j];
                u32 v = y[j + half];
                u32 s = u + v; if (s >= MOD) s -= MOD;
                u32 d = u - v; if (d >= MOD) d += MOD;  // u-v wraps unsigned
                y[j] = s;
                y[j + half] = (u32)((u64)d * rts[j * step] % MOD);
            }
        }
    }
}

// inverse DIT (input bit-reversed, output natural)
static inline void ntt_inv(u32 *x, int n, const u32 *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) {
            u32 *y = x + i;
            for (int j = 0; j < half; j++) {
                u32 u = y[j];
                u32 v = (u32)((u64)y[j + half] * rts[j * step] % MOD);
                u32 s = u + v; if (s >= MOD) s -= MOD;
                u32 d = u - v; if (d >= MOD) 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] = (u32)readint();
    for (int i = 0; i < nb; i++) b[i] = (u32)readint();

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

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

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

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

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

评测结果