代码

#include<cstdio>
#include<algorithm>
typedef long long ll;
const int N=100005,M=3*N,Mod=998244353;
int a[M],b[M],r[M],n1,n2,m,l;
#define mul(x,y) (1ll*x*y%Mod)
inline int po(int x, int y) {
	int r=1;
	while(y) {
		if(y&1) r=mul(r,x);
		x=mul(x,x),y>>=1;
	}
	return r;
}
void init(int x)
{
	for(m=1,l=0;m<=x;++l,m<<=1);
	for(int i=0;i<m;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}
void ntt(int* a, int f)
{
	for(int i=0;i<m;++i) if(i<r[i]) std::swap(a[i],a[r[i]]);
	for(int i=1;i<m;i<<=1)
	{
		int wn=po(3,(Mod-1)/(i<<1)),w=1;
		if(f==-1) wn=po(wn,Mod-2);
		for(int j=0;j<m;j+=i<<1,w=1)
			for(int k=0;k<i;++k,w=mul(w,wn))
			{
				int x=a[j+k],y=mul(w,a[i+j+k]);
				a[j+k]=(x+y)%Mod, a[i+j+k]=(x-y+Mod)%Mod;
			}
	}
	if(f==-1)
	{
		ll in=po(m,Mod-2);
		for(int i=0;i<m;++i) a[i]=mul(a[i],in);
	}
}
int main()
{
#ifdef lc
	freopen("ntt.in","r",stdin);
#endif
	scanf("%d%d",&n1,&n2);
	for(int i=0;i<=n1;++i) scanf("%d",&a[i]);
	for(int i=0;i<=n2;++i) scanf("%d",&b[i]);
	init(n1+n2+2);
	ntt(a,1),ntt(b,1);
	for(int i=0;i<m;++i) a[i]=mul(a[i],b[i]);
	ntt(a,-1);
	for(int i=0;i<=n1+n2;++i) printf("%d ",a[i]);
}

评测结果