代码

// edit from yty

#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define DEC(i, a, b) for (int i = (a); i >= (b); --i)
#define il inline
#define clr(f, n) memset(f, 0, (sizeof(INT)) * (n))
#define cpy(f, g, n) memcpy(f, g, (sizeof(INT)) * (n))
#define MOD 998244353

template<typename T> il T min(T a, T b) {return a < b ? a : b;}
template<typename T> il T max(T a, T b) {return a > b ? a : b;}

namespace poly {
    typedef int INT;
    typedef unsigned long long ull;
    typedef long long ll;
    using std::vector;
    typedef vector<INT> Poly;

    INT qPow(INT a, INT b, INT p = MOD) {
        INT ret = 1;
        for (; b; b >>= 1, a = 1ll * a * a % p)
            if (b & 1) ret = 1ll * ret * a % p;
        return ret;
    }

    const INT mod = MOD, G = 3, invG = qPow(G, mod - 2);
    const int maxn = ((1 << 22) + 500);

    int rev[maxn << 1], revLim, lim;

    void getRev(int lim) {
        if (lim == revLim) return;
        revLim = lim;
        FOR(i, 0, revLim - 1)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
        return;
    }
    
    void NTT(INT* g, int n, int type) {
        getRev(n);
        static ull f[maxn << 1], w[maxn];
        w[0] = 1;
        FOR(i, 0, n - 1)
            f[i] = (((long long)mod << 5ll) + g[rev[i]]) % mod;
        for (int l = 1; l < n; l <<= 1)         {
            ull tmp = qPow(type ? G : invG, (mod - 1) / (l << 1));
            FOR(i, 1, l - 1) w[i] = w[i - 1] * tmp % mod;
            for (int i = 0; i < n; i += (l << 1)) {
                for (int j = 0; j < l; ++j) {
                    ll tt = w[j] * f[i + j + l] % mod;
                    f[i + j + l] = f[i + j] + mod - tt;
                    f[i + j] += tt;
                }
            }
            if (l == (1 << 10))
                FOR(i, 0, n - 1) f[i] %= mod;
        }
        if (!type) {
            ull invn = qPow(n, mod - 2);
            FOR(i, 0, n - 1) g[i] = f[i] % mod * invn % mod;
        } else FOR(i, 0, n - 1) g[i] = f[i] % mod;
        return;
    }

    void mul(INT *f, INT *g, int m) {
        FOR(i, 0, m - 1) f[i] = 1ll * f[i] * g[i] % mod;
        return;
    }

    Poly operator+(const Poly &f, const Poly &g) {
        Poly h = f; h.resize(max(f.size(), g.size()));
        for (int i = 0; i < g.size(); ++i) h[i] = (h[i] + g[i]) % mod;
        return h;
    }

    Poly operator-(const Poly &f, const Poly &g) {
        Poly h = f; h.resize(max(f.size(), g.size()));
        for (int i = 0; i < g.size(); ++i) h[i] = (h[i] - g[i] + mod) % mod;
        return h;
    }

    Poly operator*(const INT lambda, const Poly &f) {
        Poly h = f;
        for (int i = 0; i < f.size(); ++i) h[i] = 1ll * h[i] * lambda % mod;
        return h;
    }

    Poly operator*(Poly &f, Poly &g) {
        static INT a[maxn << 1], b[maxn << 1];
        cpy(a, &f[0], f.size());
        cpy(b, &g[0], g.size());
        Poly ret; ret.resize(min(lim, (int)(f.size() + g.size() - 1)));
        //printf("%d %d\n", lim, f.size() + g.size() - 1);
        int n; for (n = 1; n < (int)f.size() + (int)g.size() - 1; n <<= 1);
        NTT(a, n, 1), NTT(b, n, 1);
        mul(a, b, n), NTT(a, n, 0);
        cpy(&ret[0], a, ret.size());
        clr(a, n), clr(b, n);
        return ret;
    }

    void polyInv(INT *f, int m) {
        int n;
        for (n = 1; n < m; n <<= 1);
        static INT w[maxn << 1], r[maxn << 1], sav[maxn << 1];
        w[0] = qPow(f[0], mod - 2);
        for (int len = 2; len <= n; len <<= 1) {
            FOR(i, 0, (len >> 1) - 1)
                r[i] = 2 * w[i] % mod;
            cpy(sav, f, len);
            NTT(w, len << 1, 1);
            FOR(i, 0, (len << 1) - 1) w[i] = 1ll * w[i] * w[i] % mod;
            NTT(sav, len << 1, 1);
            FOR(i, 0, (len << 1) - 1) w[i] = 1ll * w[i] * sav[i] % mod;
            NTT(w, len << 1, 0);
            clr(w + len, len);
            FOR(i, 0, len - 1)
                w[i] = (r[i] - w[i] + mod) % mod;
        }
        cpy(f, w, m);
        clr(sav, n << 1), clr(w, n << 1), clr(r, n << 1);
    }

    INT inv[maxn];
    void initInv(int lim) {
        inv[1] = 1;
        FOR(i, 2, lim)
            inv[i] = 1ll * inv[MOD % i] * (mod - MOD / i) % mod;
        return;
    }

    void derivate(INT *f, int m) {
        FOR(i, 1, m - 1)
            f[i - 1] = 1ll * i * f[i] % mod;
        f[m - 1] = 0;
    }

    void intergrate(INT *f, int m) {
        DEC(i, m, 1)
            f[i] = 1ll * f[i - 1] * inv[i] % mod;
        f[0] = 0;
        return;
    }

    void polyLn(INT *f, int m) {
        static INT invf[maxn << 1];
        int lim = 1;
        while (lim < m << 1) lim <<= 1;
        cpy(invf, f, m);
        polyInv(invf, m);
        derivate(f, m);
        //times(f, invf, lim, lim);
        intergrate(f, m);
        clr(invf, lim);
        clr(f + m, lim - m);
        return;
    }

    void polyExp(INT *f, int m) {
        int n;
        for (n = 1; n < m; n <<= 1);
        static INT s[maxn << 1], s2[maxn << 1];
        s2[0] = 1;
        for (int len = 2; len <= n; len <<= 1) {
            cpy(s, s2, len >> 1);
            polyLn(s, len);
            FOR(i, 0, len - 1) s[i] = (f[i] - s[i] + mod) % mod;
            s[0] = (s[0] + 1) % mod;
            //times(s2, s, len, len);
        }
        cpy(f, s2, m), clr(s, n << 1), clr(s2, n << 1);
        return;
    }

    void polySqrt(INT *f, int m) {
        int n;
        for (n = 1; n < m; n <<= 1);
        static int b1[maxn << 1], b2[maxn << 1];
        b1[0] = 1;
        for (int len = 2; len <= n; len <<= 1) {
            for (int i = 0; i < (len >> 1); ++i) b2[i] = (b1[i] << 1) % mod;
            polyInv(b2, len);
            NTT(b1, len, 1);
            FOR(i, 0, len - 1) b1[i] = 1ll * b1[i] * b1[i] % mod;
            NTT(b1, len, 0);
            FOR(i, 0, len - 1) b1[i] = (b1[i] + f[i]) % mod;
            //times(b1, b2, len, len);
        }
        cpy(f, b1, m), clr(b1, n << 1), clr(b2, n << 1);
        return;
    }
} using namespace poly;

namespace fastIO {
    const int maxc = 1 << 23;
    char ibuf[maxc], *__p1 = ibuf, *__p2 = ibuf;
    il char getchar() {return __p1 == __p2 && (__p2 = (__p1 = ibuf) + fread(ibuf, 1, maxc, stdin), __p1 == __p2) ? EOF : *__p1++;}
    template<typename T> void read(T &n) {
        int x = 0; n = 0;
        char c = getchar();
        while (!isdigit(c))
            x |= (c == '-'), c = getchar();
        while (isdigit(c))
            n = n * 10 + c - '0', c = getchar();
        n = x ? -n : n;
    }
    void read(char *s) {
        int p = 0;
        char c = getchar();
        while (!isdigit(c) && !isalpha(c)) c = getchar();
        while (isalpha(c) || isdigit(c)) s[p++] = c, c = getchar();
        return;
    }
    char obuf[maxc], *__pO = obuf;
    il void putchar(char c) {*__pO++ = c;}
    template<typename T> void print(T x) {
        if (x < 0) putchar('-'), print(-x);
        else {
            if (x > 9) print(x / 10);
            putchar(x % 10 + '0');
        }
        return;
    }
    void print(Poly f) {
        for (int i = 0; i < f.size(); ++i) print(f[i]), putchar(' ');
        putchar('\n');
    }
    void output() {fwrite(obuf, __pO - obuf, 1, stdout);}
} using namespace fastIO;


int n, m;
Poly f, g;

int main() {
    read(n), read(m);
    f.resize(n + 1), g.resize(m + 1);
    FOR(i, 0, n) read(f[i]);
    FOR(i, 0, m) read(g[i]);
    lim = n + m + 1;
    f = f * g;
    print(f);
    return output(), 0;
}

评测结果