代码

#pragma GCC optimize( "unroll-loops" )
#pragma GCC optimize( "O2" )
#include <bits/stdc++.h>

#define IL inline
#define CT const
#define RG register
#define TT template <typename Ty>

namespace io
{
const int MaxBuff = 1 << 24, MaxOut = 1 << 24;
char b[MaxBuff], *S = b, *T = b, buff[MaxOut], *iter = buff;
FILE *_IN = stdin, *_OUT = stdout;
IL char gc() { return S == T && (T = (S = b) + fread(b, 1, MaxBuff, _IN), S == T) ? 0 : *S++; }
IL void pc(const char s) { *iter++ = s; }
IL void fflush() { fwrite(buff, 1, iter - buff, _OUT), iter = buff, fclose(_IN), fclose(_OUT); }
} // namespace io

TT IL Ty max(CT Ty &a, CT Ty &b) { return a > b ? a : b; }
TT IL Ty min(CT Ty &a, CT Ty &b) { return a < b ? a : b; }
TT IL void cmax(Ty &a, CT Ty &b) { if (b > a) a = b; }
TT IL void cmin(Ty &a, CT Ty &b) { if (b < a) a = b; }
TT IL void swap(Ty &a, Ty &b) { Ty t = a; a = b; b = t; }
TT IL void swap(Ty *&a, Ty *&b) { Ty *t = a; a = b; b = t; }

TT IL void read(Ty &t)
{
    t = 0;
    int f = 1;
    RG char ch = io::gc();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = io::gc();
    }
    do
    {
        t = t * 10 + ch - '0';
        ch = io::gc();
    } while (ch >= '0' && ch <= '9');
    t *= f;
}

TT IL void write(Ty x)
{
    if (x < 0)
        io::pc('-');
    if (x > 9)
        write(x / 10);
    io::pc(x % 10 + '0');
}

typedef long long ll;
const int wcz = 998244353;
const int N = 1e6 + 5;

IL int addint( int x ) { return x >= wcz ? x - wcz : x; }
IL int addint( int x, int y ) { return addint(x + y); }
IL int qpow( int a, int b )
{
	int res = 1;
	for ( ; b; b >>= 1, a = ((ll)a * a) % wcz )
		if ( b & 1 ) res = ((ll)res * a) % wcz;
	return res;
}

namespace poly
{
int w[N * 4];

void dit(int n, int *a)
{
    for (int m = 1; m < n; m <<= 1)
    {
        int root = qpow(3, (wcz - 1) / (m << 1));
        w[0] = 1;
        for (int i = 1; i < m; ++i)
            w[i] = ((ll)w[i - 1] * root) % wcz;
        for (int i = 0; i < n; i += m << 1)
            for (int r = i; r < i + m; ++r)
            {
                int tmp = ((ll)w[r - i] * a[r + m]) % wcz;
                a[r + m] = addint(a[r], wcz - tmp);
                a[r] = addint(a[r], tmp);
            }
    }
}

void dif(int n, int *a)
{
    for (int m = n; m >>= 1;)
    {
        int root = qpow(3, wcz - 1 - (wcz - 1) / (m << 1));
        w[0] = 1;
        for (int i = 1; i < m; ++i)
            w[i] = ((ll)w[i - 1] * root) % wcz;
        for (int i = 0; i < n; i += m << 1)
            for (int r = i; r < i + m; ++r)
            {
                int tmp = addint(a[r], wcz - a[r + m]);
                a[r] = addint(a[r], a[r + m]);
                a[r + m] = ((ll)w[r - i] * tmp) % wcz;
            }
    }
}

void convolute(int n, int *a, int *b, int *out)
{
    dif(n, a);
    dif(n, b);
    unsigned long long inv_n = qpow(n, wcz - 2);
    for (int i = 0; i < n; ++i)
        out[i] = (((ll)inv_n * a[i]) % wcz * b[i]) % wcz;
    dit(n, out);
}
} // namespace poly

int n, m, a[N * 4], b[N * 4];

int main()
{
    read(n), read(m);
    ++n, ++m;
    for (int i = 0; i < n; ++i)
        read(a[i]);
    for (int i = 0; i < m; ++i)
        read(b[i]);
    int n2 = 1;
    while (m + n >= n2)
        n2 <<= 1;
    poly::convolute(n2, a, b, a);
    for (int i = 0; i < n + m - 1; ++i)
        write(a[i]), io::pc(' ');
    io::pc('\n');
    io::fflush();
    return 0;
}

评测结果