代码

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

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 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);}

int n,m; 

std::vector<int>p1,p2,ans;
namespace Poly
{
	int og[M+5];
	inline void init(int l)
	{
		og[1]=1;
		for(int i=2;i<l;i<<=1)
			for(int j=i,e=ksm(G,(P-1)/(i*2));j<i*2;j+=2)
				og[j]=og[j>>1],og[j|1]=1ll*og[j]*e%P;
	}
	inline void dif(std::vector<int>&a)
	{
		int l=a.size();
		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(std::vector<int>&a)
	{
		int l=a.size();
		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=P-(P-1)/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]);
	}
	inline void mul(std::vector<int>&a,std::vector<int>&b,std::vector<int>&c)
	{
		int la=a.size(),lb=b.size(),l=upb(la+lb-1);
		
		std::vector<int>ca=a,cb=b;
		
		a.resize(l),b.resize(l);
		dif(a),dif(b);
		
		c.resize(l);
		for(int i=0;i<l;++i)c[i]=1ll*a[i]*b[i]%P;
		idft(c);
		c.resize(la+lb-1);
		
		std::swap(a,ca),std::swap(b,cb);
	}
};

int main()
{
//	freopen("ntt.in","r",stdin),freopen("ntt.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	p1.resize(n+1),p2.resize(m+1);
	for(int i=0;i<=n;++i)scanf("%d",&p1[i]);
	for(int i=0;i<=m;++i)scanf("%d",&p2[i]);
	
	Poly::init(upb(n+m+1));
	Poly::mul(p1,p2,ans);
	
	for(int x:ans)printf("%d ",x);
	puts("");

	return 0;
}

评测结果