代码

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int N=3e6+10;
const int p=998244353;
const int g=3;
const int invg=332748118;
int rev[N],A[N],B[N];
int POW(int a,int b)
{
	if(!b) return 1;
	if(b==1) return a;
	int sum=POW(a,b/2);
	if(b%2) return sum*sum%p*a%p;
	return sum*sum%p;
}
void NTT(int *a,int tp,int n)
{
	for(int i=0;i<n;i++)
		if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int l=1;l<n;l*=2)
	{
		int w=POW(tp?g:invg,(p-1)/(l*2));
		for(int i=0;i<n;i+=l*2)
		{
			int W=1;
			for(int k=0;k<l;k++,W=W*w%p)
			{
				int x=a[i+k],y=W*a[i+k+l]%p;
				a[i+k]=(x+y)%p,a[i+k+l]=(x-y+p)%p;
			}
		}
	}
}
signed main()
{
	int n,m,t=1,O=0;
	scanf("%lld%lld",&n,&m);
	for(int i=0;i<=n;i++) scanf("%lld",&A[i]);
	for(int i=0;i<=m;i++) scanf("%lld",&B[i]);
	while(t<=n+m) t*=2,O++;
	for(int i=0;i<=t;i++)
		rev[i]=(rev[i/2]/2)+(1<<O-1)*(i%2);
	NTT(A,1,t),NTT(B,1,t);
	for(int i=0;i<=t;i++) A[i]=A[i]*B[i]%p;
	NTT(A,0,t);
	int inv=POW(t,p-2);
	for(int i=0;i<=n+m;i++) printf("%lld ",A[i]*inv%p);
	return 0;
}

评测结果