代码

#include<cstdio>
#include<algorithm>
#include<cassert>
#include<ctime>
const int N=1<<20,M=1<<21,P=998244353,G=3;

int n,m,f[M+5],g[M+5],h[M+5],og[M+5];

inline int ksm(int x,int y){int z=1;for(;y;x=1ll*x*x%P,y>>=1)if(y&1)z=1ll*z*x%P;return z;}
inline int inv(int x){return ksm(x,P-2);}
inline int upb(int x){--x,x|=x>>1,x|=x>>2,x|=x>>4,x|=x>>8,x|=x>>16;return x+1;}
inline void ntt_init(int l)
{
	if(l>1)og[1]=1;
	for(int i=2;i<l;i<<=1)
	{
		int e=ksm(G,(P-1)/(i*2));
		for(int j=i;j<i*2;j+=2)og[j]=og[j>>1],og[j|1]=1ll*og[j]*e%P;
	}
}
inline void dif(int a[],int l)
{
	for(int i=l>>1;i;i>>=1)for(int j=0;j<l;j+=i*2)for(int k=0;k<i;++k)
	{
		int x=a[j|k],y=a[j|i|k];
		a[j|k]=(x+y)%P,a[j|i|k]=1ll*(x+P-y)*og[i|k]%P;
	}
}
inline void idft(int a[],int l)
{
	for(int i=1;i<l;i<<=1)for(int j=0;j<l;j+=i*2)for(int k=0;k<i;++k)
	{
		int x=a[j|k],y=1ll*a[j|i|k]*og[i|k]%P;
		a[j|k]=(x+y)%P,a[j|i|k]=(x+P-y)%P;
	}
	for(int i=0,z=inv(l);i<l;++i)a[i]=1ll*a[i]*z%P;
	for(int i=1;i<l-i;++i)std::swap(a[i],a[l-i]); 
}

int main()
{
//	freopen("ntt.in","r",stdin);
//	freopen("ntt.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;++i)scanf("%d",&f[i]);
	for(int i=0;i<=m;++i)scanf("%d",&g[i]);
	
	int l=upb(n+m+1);
	ntt_init(l);
	dif(f,l),dif(g,l);
	for(int i=0;i<l;++i)f[i]=1ll*f[i]*g[i]%P;
	idft(f,l);
	
	for(int i=0;i<=n+m;++i)printf("%d ",f[i]);
	puts("");
	
	return 0;
}

评测结果