代码

//review ntt
#include<bits/stdc++.h>
using namespace std;
const int LEN=1<<19;
#define uint unsigned int
inline char gc(){
	static char buf[LEN+10],*PT=buf,*PTEND=buf+LEN;
	return ((PT==PTEND)&&(fread(buf,1,LEN,stdin),PT=buf)),*(PT++);
}
inline uint getint(){
	uint ans=0;
	char c=gc();
	while(c<'0'||c>'9')c=gc();
	while(c>='0'&&c<='9'){
		ans=ans*10+c-'0';
		c=gc();
	}
	return ans;
}
const int N=4e6+10,mod=998244353,G=3;

int w[N],iw[N];
int a[N],b[N],c[N];
int rev[N];

int qpow(int x,int y){
	int ans=1;
	while(y){
		if(y&1)ans=ans*1ll*x%mod;
		x=x*1ll*x%mod;
		y>>=1;
	}
	return ans;
}
void ntt(int *a,int n,int r=1){
	int *W=(~r?w:iw);
	for(int i=0;i<n;i++)
		if(i>rev[i])swap(a[i],a[rev[i]]);
	for(int i=1;i<n;i<<=1){
		int d=n/i/2;
		for(int j=0;j<n;j+=i<<1){
			int t=0;
			for(int k=0;k<i;k++,t+=d){
				int x=a[j+k],y=W[t]*1ll*a[j+k+i]%mod;
				a[j+k]=(x+y)%mod;
				a[j+k+i]=(x-y+mod)%mod;
			}
		}
	}
	if(r==-1){
		int invn=qpow(n,mod-2);
		for(int i=0;i<n;i++){
			a[i]=a[i]*1ll*invn%mod;
		}
	}
}
void init_w(int n){
	w[0]=iw[0]=1;
	w[1]=qpow(G,(mod-1)/n);
	iw[1]=qpow(w[1],mod-2);
	for(int i=2;i<n;i++)
		w[i]=w[i>>1]*1ll*w[i>>1]%mod*w[i&1]%mod,
		iw[i]=iw[i>>1]*1ll*iw[i>>1]%mod*iw[i&1]%mod;
}

int main(){
	int n=getint(),m=getint();
	int nm=1,l=0;
	while(nm<=n+m)nm<<=1,l++;
	for(int i=1;i<nm;i++)
		rev[i]=rev[i>>1]>>1|((i&1)<<(l-1));
	init_w(nm);
	for(int i=0;i<=n;i++)a[i]=getint();
	for(int i=0;i<=m;i++)b[i]=getint();
	ntt(a,nm);
	ntt(b,nm);
	for(int i=0;i<nm;i++)c[i]=a[i]*1ll*b[i]%mod;
	ntt(c,nm,-1);
	for(int i=0;i<=m+n;i++)printf("%d ",c[i]);
	return 0;
}

评测结果