代码

// v1: baseline NTT mod 998244353, standard DIT with bitrev, fast 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 inline int modpow(int base, i64 e) {
    i64 r = 1, b = base % MOD;
    for (; e; e >>= 1) {
        if (e & 1) r = r * b % MOD;
        b = b * b % MOD;
    }
    return (int)r;
}

static void ntt(int *x, int n, bool inv) {
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) { int t = x[i]; x[i] = x[j]; x[j] = t; }
    }
    for (int len = 2; len <= n; len <<= 1) {
        int wlen = modpow(G, (MOD - 1) / len);
        if (inv) wlen = modpow(wlen, MOD - 2);
        int half = len >> 1;
        for (int i = 0; i < n; i += len) {
            i64 w = 1;
            int *y = x + i;
            for (int j = 0; j < half; j++) {
                int u = y[j];
                int v = (int)(y[j + half] * w % 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;
                w = w * wlen % MOD;
            }
        }
    }
    if (inv) {
        int ninv = modpow(n, MOD - 2);
        for (int i = 0; i < n; i++) x[i] = (int)((i64)x[i] * ninv % MOD);
    }
}

// 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;

    ntt(a, size, false);
    ntt(b, size, false);
    for (int i = 0; i < size; i++) a[i] = (int)((i64)a[i] * b[i] % MOD);
    ntt(a, size, true);

    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;
}

评测结果