代码

#include <bits/stdc++.h>
using namespace std;
using Z = uint64_t;
using LZ = __uint128_t;
const Z P = 998244353, Pneg = Z((LZ(1) << 64) / 998244353);
namespace FastMod {
    inline Z mod(Z x) {
        Z q = Z((LZ(x) * Pneg) >> 64);
        Z r = x - q * P;
        return r >= P ? r - P : r;
    }
    inline Z add(Z a, Z b) {
        return (a + b >= P) ? (a + b - P) : (a + b);
    }
    inline Z sub(Z a, Z b) {
        return (a - b >= P) ? (a - b + P) : (a - b);
    }
}
const int Nn = 21;
namespace Poly {
    Z rev[1 << Nn], idf[1 << Nn], Inv[Nn + 1];
    const Z G23 = 733596141, Inv2 = 499122177;
    void prepare() {
        for (int i = 0; i < (1 << (Nn - 1)); ++ i) {
            rev[i << 1] = rev[i] >> 1;
            rev[(i << 1) | 1] = (rev[i] >> 1) | (1 << (Nn - 1));
        }
        idf[0] = 1;
        for (int i = 1; i < (1 << Nn); ++ i) {
            idf[i] = FastMod::mod(idf[i - 1] * G23);
        }
        Inv[0] = 1;
        for (int i = 1; i <= Nn; ++ i)
            Inv[i] = FastMod::mod(Inv[i - 1] * Inv2);
    }
    inline Z w(Z lg, Z x) {
        return idf[x << (Nn - lg)];
    }
    inline Z r(Z lg, Z x) {
        return rev[x] >> (Nn - lg);
    }
    void butterfly(Z *a, Z lg) {
        for (int i = 0; i < (1 << lg); ++ i) {
            if (i < r(lg, i)) swap(a[i], a[r(lg, i)]);
        }
    } 
    void FFT(Z *a, Z lg, bool f) {
        butterfly(a, lg);
        Z b;
        for (int i = 0; i < lg; ++ i)
            for (int j = 0; j < (1 << lg); j += (2 << i))
                for (int k = 0; k < (1 << i); ++ k)
                    b = FastMod::mod(w(i + 1, k) * a[(1 << i) + j + k]),
                    a[(1 << i) + j + k] = FastMod::sub(a[j + k], b),
                    a[j + k] = FastMod::add(a[j + k], b);
        if (f) {
            reverse(a + 1, a + (1 << lg));
            for (int i = 0; i < (1 << lg); ++ i)
                a[i] = FastMod::mod(a[i] * Inv[lg]);
        }
    }
    void mul(Z *a, Z *b, Z lg) {
        FFT(a, lg + 1, 0); FFT(b, lg + 1, 0);
        for (int i = 0; i < (2 << lg); ++ i)
            a[i] = FastMod::mod(a[i] * b[i]);
        FFT(a, lg + 1, 1);
    }
    void inv(Z *a, Z lg) {
        
    }
}
namespace FastIO {
    const int N = 1048576 + 666;
    char buf[N], wrt[N];
    char * c = buf + 1048576;
    char *ed = buf + 1048576;
    char * d = wrt;
    char *ef = wrt + 1048576;
    #define gtc() \
        if (c == ed) { \
            fread(buf, 1, 1048576, stdin); \
            c = buf; \
        } \
        cc = *(c ++)
    Z read() {
        Z ans = 0, fl = +1;
        char cc = 0;
        while (!isdigit(cc)) {
            if (cc == '-') fl = -1;
            gtc();
        }
        while (isdigit(cc)) {
            ans = ans * 10 + (cc - '0');
            gtc();
        }
        return ans;
    }
    #define ptc(x) \
        if (d == ef) { \
            fwrite(wrt, 1, 1048576, stdout); \
            memset(wrt, 0, sizeof wrt); \
            d = wrt; \
        } \
        *(d ++) = x;
    void write(Z x) {
        if (x < 0) {
            ptc('-');
            x = -x;
        }
        static int orz[35] = {' ' - '0'};
        int top = 1;
        do {
    		orz[top++] = x % 10;
    		x /= 10;
    	} while (x);
    	while (top) {ptc(orz[--top] + '0');};
    	
    }
    void shut() {
        fwrite(wrt, 1, sizeof(wrt), stdout);
    }
}
int main() {
    Poly::prepare();
    Z a[1 << 21] = {}, b[1 << 21] = {};
    int n = FastIO::read(), m = FastIO::read();
    for (int i = 0; i <= n; ++ i) a[i] = FastIO::read();
    for (int i = 0; i <= m; ++ i) b[i] = FastIO::read();
    Poly::mul(a, b, __lg(max(n, m)) + 1);
    for (int i = 0; i <= n + m; ++ i) FastIO::write(a[i]);
    FastIO::shut();
}

评测结果