代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 10
#define N1 2100010
#define P 998244353
#define g 3
using namespace std;
typedef long long  ll;
int n,m,N,rev[N1],lg;
char s[1000010],stk[10];
ll ans[N1],a[N1],b[N1];
ll ksm(ll x,ll y,ll p)
{
	ll res = 1;
	while(y > 0)
	{
		if(y & 1) res = res * x % p;
		x = x * x % p;
		y = y >> 1;
	}
	return res;
}
void NTT(ll a[],int xs)
{
	int l = 1;
	for(int i = 0;i < N;i++)
	{
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << lg - 1);
		if(i < rev[i])
		{
			ll t = a[i];
			a[i] = a[rev[i]];
			a[rev[i]] = t;
		}
	}
	int mi = 1;
	for(int i = 1;i <= lg;i++)
	{
		ll w = ksm(g,(P - 1) >> i,P);
		if(xs == -1) w = ksm(w,P - 2,P);
		for(int j = 0;j < N;j += (1 << i))
		{
			ll w1 = 1;
			for(int k = 0;k < mi;k++)
			{
				ll t = w1 * a[j + k + mi] % P,u = a[j + k];
				a[j + k] = (u + t) % P;
				a[j + k + mi] = (u - t + P) % P;
				w1 = w1 * w % P;
			}
		}
		mi = (mi << 1) % P;
	}
	if(xs == -1)
	{
		ll ny = ksm(N,P - 2,P);
		for(int i = 0;i < N;i++) a[i] = a[i] * ny % P;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 0;i <= n;i++) scanf("%lld",&a[i]);
	for(int i = 0;i <= m;i++) scanf("%lld",&b[i]);
	N = 1;
	while(N <= m + n)
	{
		N = N << 1;
		lg++;
	}
	NTT(a,1);
	NTT(b,1);
	for(int i = 0;i < N;i++) a[i] = a[i] * b[i] % P;
	NTT(a,-1);
	for(int i = 0;i <= n + m;i++) printf("%lld ",a[i]);
	return 0;
}

评测结果