代码

#include<cstdio>
typedef unsigned ui;
typedef unsigned long long ull;
const ui N=1048576u,M=2097152u,P=998244353u,G=3u;
ui n,m,f[M+5u],g[M+5u];

ui og[M+5u];
inline ui upb(ui x){x|=x>>1u,x|=x>>2u,x|=x>>4u,x|=x>>8u,x|=x>>16u;return x+1u;}
inline void rev(ui*l,ui*r){ui z;for(;l<r;z=*l,*l++=*r,*r--=z);}
inline ui ksm(ui x,ui y){ui z=1u;for(;y;x=(ull)x*x%P,y>>=1u)if(y&1u)z=(ull)z*x%P;return z;}
inline void Tii(ui x)
{
	if(x==1)return;
	og[x>>1]=1;
	for(ui i=(x>>1)+1,e=ksm(G,(P-1)/x);i<x;++i)
		og[i]=1ll*og[i-1]*e%P;
	for(ui i=(x>>1)-1;i;--i)og[i]=og[i<<1];
}
inline void DIF(ui*tf,ui x)
{
	for(ui i=x>>1u;i;i>>=1u)
		for(ui j=0u;j<x;j+=i<<1u)
			for(ui k=0u,z;k<i;++k)
			{
				z=(ull)(tf[j|k]+P-tf[j|i|k])*og[i|k]%P;
				(tf[j|k]+=tf[j|i|k])%=P,tf[j|i|k]=z;
			}
}
inline void DFT(ui*tf,ui x)
{
	for(ui i=1u;i<x;i<<=1u)
		for(ui j=0u;j<x;j+=i<<1u)
			for(ui k=0u,z;k<i;++k)
			{
				z=(ull)og[i|k]*tf[j|i|k]%P;
				tf[j|i|k]=(tf[j|k]+P-z)%P,(tf[j|k]+=z)%=P;
			}
	for(ui i=0u,z=P-(P-1u)/x;i<x;++i)
		tf[i]=(ull)tf[i]*z%P;
	rev(tf+1u,tf+x-1);
}

int main()
{
	scanf("%u%u",&m,&n);
	for(ui i=0u;i<=m;++i)scanf("%u",&f[i]);
	for(ui i=0u;i<=n;++i)scanf("%u",&g[i]);
	
	n+=m,m=upb(n);
	Tii(m);
	DIF(f,m),DIF(g,m);
	for(ui i=0u;i<m;++i)
		f[i]=(ull)f[i]*g[i]%P;
	DFT(f,m);
	
	for(ui i=0u;i<=n;++i)
		printf("%u ",f[i]);
	puts("");
	
	return 0;
}

评测结果