代码

#include<cstdio>
const int N=262151,P=998244353;
int n,r[N],a[N],b[N];
int qp(int a,int b){
	int r=1;
	for(;b;b>>=1,a=a*1ll*a%P)if(b&1)r=r*1ll*a%P;
	return r;
}
void ntt(int*a,bool b){
	int i,j,k,l,p,u,v,x,y;
	for(i=0;i<n;++i)if(i<r[i])j=a[i],a[i]=a[r[i]],a[r[i]]=j;
	for(i=1;i<n;i<<=1)
	for(l=i<<1,u=qp(b?3:332748118,(P-1)/l),j=0;j<n;j+=l)
	for(v=1,k=j,p=j+i;k<p;++k,v=v*1ll*u%P)
	x=a[k],y=v*1ll*a[i+k]%P,a[k]=(a[k]=x+y)<P?a[k]:a[k]-P,a[i+k]=x<y?x-y+P:x-y;
}
int main(){
	int m,i,l=-1;
	scanf("%d%d",&n,&m);
	for(i=0;i<=n;++i)scanf("%d",a+i);
	for(i=0;i<=m;++i)scanf("%d",b+i);
	for(m+=n,n=1;n<=m;n<<=1)++l;
	for(i=0;i<n;++i)r[i]=(r[i>>1]>>1)|((i&1)<<l);
	ntt(a,1),ntt(b,1);
	for(i=0;i<n;++i)a[i]=a[i]*1ll*b[i]%P;
	ntt(a,0),l=qp(n,P-2);
	for(i=0;i<=m;++i)printf("%d ",a[i]*1ll*l%P);
	return 0;
}

评测结果