代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = (1 << 21) + 1005;
const int P = 998244353, G = 3, Gi = 332748118;
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read() { 
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
inline void print(int X)
{
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) print(X/10);
    putchar(X%10+'0');
}

LL fsp(LL a, int b = P - 2)
{
	LL s = 1;
	while (b)
	{
		if (b & 1)
			s = s * a % P;
		b >>= 1, a = a * a % P;
	}
	return s;
}
int rev[maxn], lim;
int W[maxn], CW[maxn];
void Init(int len)
{
	int l = 0;
	lim = 1;
	while (lim <= len)
		lim <<= 1, ++l;
	W[0] = CW[0] = 1;
	int Wp = fsp(G, (P - 1) / lim), Cp = fsp(Gi, (P - 1) / lim);
	for (int i = 1; i < lim; i++)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1)), W[i] = 1ll*W[i - 1] * Wp % P, CW[i] = 1ll*CW[i - 1] * Cp % P;
}
struct Poly
{
	int num[maxn];
	void NTT(int type)
	{
		for (int i = 0; i < lim; i++)
			if (i < rev[i])
				swap(num[i], num[rev[i]]);
		if (type == 1)
		{
			for (int t = (lim >> 1), m = 1; m < lim; m <<= 1, t >>= 1)
			{
				for (int i = 0; i < lim; i += (m << 1))
				{
					for (int j = 0; j < m; j++)
					{
						LL x = num[i + j], y = 1ll * W[t * j] * num[i + j + m] % P;
						num[i + j] = (x + y) % P;
						num[i + j + m] = (x - y + P) % P;
					}
				}
			}
		}else{
			for (int t = lim >> 1, m = 1; m < lim; m <<= 1, t >>= 1)
			{
				for (int i = 0; i < lim; i += (m << 1))
				{
					for (int j = 0; j < m; j++)
					{
						int x = num[i + j], y = 1ll * CW[t * j] * num[i + j + m] % P;
						num[i + j] = (x + y) % P;
						num[i + j + m] = (x - y + P) % P;
					}
				}
			}
			int invlen=fsp(lim);
			for(int i=0;i<lim;i++)num[i]=1ll*num[i]*invlen%P;
		}
	}
};
Poly a,b;
int main()
{
	int n,m;
	n=read(),m=read();
	for(int i=0;i<=n;i++)a.num[i]=read();
	for(int i=0;i<=m;i++)b.num[i]=read();
	Init(n+m);
	a.NTT(1),
	b.NTT(1);
	for(int i=0;i<lim;i++)a.num[i]=(1ll*a.num[i]*b.num[i])%P;
	a.NTT(-1);
	for(int i=0;i<=n+m;i++){
		printf("%d ",a.num[i]);
	}
	return 0;
}

评测结果