代码

#include <bits/stdc++.h>

struct IOprecalc {
    alignas(64) char digit[40000];
    uint64_t log[64][2];
    constexpr IOprecalc() : digit{}, log{} {
        for(int i = 0; i < 10000; i++) {
            digit[i * 4 + 0] = 48 + i / 1000;
            digit[i * 4 + 1] = 48 + i / 100 % 10;
            digit[i * 4 + 2] = 48 + i / 10 % 10;
            digit[i * 4 + 3] = 48 + i % 10;
        }
        int index = 0;
        uint64_t value = 9;
        for(int i = 0; i < 64; i++) {
            // [2^i-1, 2^(i+1)-2]
            log[i][0] = index, log[i][1] = value;
            if((2ULL << i) - 2 > value)
                index++, value = value <= (UINT64_MAX - 9) / 10 ? value * 10 + 9 : UINT64_MAX;
        }
    }
    inline __attribute((always_inline))
    void store(void* out, uint64_t k)const {
        memcpy(out, digit + k * 4, 4);
    }
};
struct IO {
    static const int inSZ = 1 << 17;
    char inBuf[inSZ], *in1, *in2;
    inline __attribute((always_inline))
    int read() {
        if(__builtin_expect(in1 > inBuf + inSZ - 32, 0)) {
            auto len = in2 - in1;
            memcpy(inBuf, in1, len);
            in1 = inBuf, in2 = inBuf + len;
            in2 += fread(in2, 1, inSZ - len, stdin);
            if(in2 != inBuf + inSZ) *in2 = 0;
        }
        int res = 0;
        char c;
        while((c = *in1++) < 48);
        while(res = res * 10 + c - 48, (c = *in1++) >= 48);
        return res;
    }
    static const int outSZ = 1 << 21;
    char outBuf[outSZ], *out;
    inline __attribute((always_inline))
    void write(uint64_t x) {
        if(__builtin_expect(out > outBuf + outSZ - 32, 0))
            fwrite(outBuf, 1, out - outBuf, stdout), out = outBuf;
        static constexpr auto P = IOprecalc();
        uint64_t bsr = __builtin_ia32_bsrdi(x + 1);
        const uint64_t B = 10000, B2 = B * B, B3 = B2 * B, B4 = B3 * B;
        uint64_t len = P.log[bsr][0] + (P.log[bsr][1] < x);
        const uint64_t extra[4] = {1000, 100, 10, 1};
        x *= extra[len & 3];
        switch(len >> 2) {
            case 0: // [0, 9999]
                P.store(out, x);
                break;
            case 1: // [10000, 99999999]
                P.store(out + 4, x - x / B * B);
                P.store(out, x / B);
                break;
            case 2:
                P.store(out + 8, x - x / B * B);
                P.store(out + 4, x / B - x / B2 * B);
                P.store(out, x / B2);
                break;
            default: __builtin_unreachable();
        }
        out += len + 2, out[-1] = ' ';
    }
    IO() {
        in1 = inBuf;
        in2 = in1 + fread(in1, 1, inSZ, stdin);
        out = outBuf;
    }
    ~IO() { fwrite(outBuf, 1, out - outBuf, stdout); }
} IO;

using namespace std;
using ll = long long;

const int N = 1 << 18, P = 998244353;

int n, lim;
ll se[22], ise[22], w[N / 2], iw[N / 2];
int a[N], b[N];

inline int add(int a, int b) { return (a += b) < P ? a : a - P; }
inline int sub(int a, int b) { return (a -= b) < 0 ? a + P : a; }
ll Pow(ll a, int n, ll r = 1) {
    for(; n; n >>= 1, a = a * a % P)
    if(n & 1) r = r * a % P;
    return r;
}
void prework() {
    ll es[22], ies[22];
    ll e = 15311432, ie = 469870224;
    for(int i = 21; i >= 0; i--)
        es[i] = e, ies[i] = ie, e = e * e % P, ie = ie * ie % P;
    ll now = 1, inow = 1;
    for (int i = 0; i <= 21; i++) {
        se[i] = es[i] * now % P, ise[i] = ies[i] * inow % P;
        (now *= ies[i]) %= P, (inow *= es[i]) %= P;
    }
}
void DIF(int a[]) {
    #define butterfly(cnt, i) \
        for(int k = 0; k < cnt; k++) { \
            int x = a[ks + k], y = a[ks + k + i] * now % P; \
            a[ks + k] = add(x, y), a[ks + k + i] = sub(x, y); \
        }
    for(int i = lim >> 1, l = 1; i; i >>= 1, l <<= 1)
        if(i == 1) for(int j = 0; j < l; j++) {
            ll now = w[j];
            int ks = j * i * 2;
            #pragma GCC unroll(1)
            butterfly(1, 1);
        } else if(i == 2) for(int j = 0; j < l; j++) {
            ll now = w[j];
            int ks = j * i * 2;
            #pragma GCC unroll(2)
            butterfly(2, 2);
        } else if(i == 4) for(int j = 0; j < l; j++) {
            ll now = w[j];
            int ks = j * i * 2;
            #pragma GCC unroll(4)
            butterfly(4, 4);
        } else for(int j = 0; j < l; j++) {
            ll now = w[j];
            int pos = j * i * 2;
            for(int ks = pos; ks < pos + i; ks += 8)
                #pragma GCC unroll(8)
                butterfly(8, i);
        }
    #undef butterfly
}
void IDIF(int a[]) {
    #define butterfly(cnt, i) \
        for(int k = 0; k < cnt; k++) { \
            int x = a[ks + k], y = a[ks + k + i]; \
            a[ks + k] = add(x, y), a[ks + k + i] = (x - y + P) * now % P; \
        }
    for(int i = 1, l = lim >> 1; l; i <<= 1, l >>= 1)
        if(i == 1) for(int j = 0; j < l; j++) {
            ll now = iw[j];
            int ks = j * i * 2;
            #pragma GCC unroll(1)
            butterfly(1, 1);
            (now *= iw[__builtin_ctz(~j)]) %= P;
        } else if(i == 2) for(int j = 0; j < l; j++) {
            ll now = iw[j];
            int ks = j * i * 2;
            #pragma GCC unroll(2)
            butterfly(2, 2);
            (now *= iw[__builtin_ctz(~j)]) %= P;
        } else if(i == 4) for(int j = 0; j < l; j++) {
            ll now = iw[j];
            int ks = j * i * 2;
            #pragma GCC unroll(4)
            butterfly(4, 4);
        } else for(int j = 0; j < l; j++) {
            ll now = iw[j];
            int pos = j * i * 2;
            for(int ks = pos; ks < pos + i; ks += 8)
                #pragma GCC unroll(8)
                butterfly(8, i);
            (now *= iw[__builtin_ctz(~j)]) %= P;
        }
    ll inv = Pow(lim, P - 2);
    if(lim < 4) for(int i = 0; i < lim; i++) a[i] = a[i] * inv % P;
    else for(int is = 0; is < lim; is += 4)
        #pragma GCC unroll(4)
        for(int i = 0; i < 4; i++) a[is + i] = a[is + i] * inv % P;
    #undef butterfly
}
int main() {
    prework();
    int n, m;
    n = IO.read(), m = IO.read();
    for(int i = 0; i <= n; i++) a[i] = IO.read();
    for(int i = 0; i <= m; i++) b[i] = IO.read();
    for(lim = 1; lim <= n + m; lim <<= 1);
    w[0] = iw[0] = 1;
    for(int i = 0; i <= (lim >> 1) - 2; i++) {
        w[i + 1] = (ll)w[i] * se[__builtin_ctz(~i)] % P;
        iw[i + 1] = (ll)iw[i] * ise[__builtin_ctz(~i)] % P;
    }
    DIF(a), DIF(b);
    for(int i = 0; i < lim; i++) a[i] = (ll)a[i] * b[i] % P;
    IDIF(a);
    for(int i = 0; i <= n + m; i++) IO.write(a[i]);
}

评测结果