代码

const unsigned N=2097152,P=998244353,G=3;
inline unsigned fix1(unsigned x){return x>=P?x-P:x;}
inline unsigned fix2(int x){return x<0?x+P:x;}
inline unsigned mul(unsigned a,unsigned b){return (unsigned long long)a*b%P;}
unsigned pw(unsigned a,unsigned n){
	unsigned v=1;
	for(;n;n>>=1,a=mul(a,a))if(n&1)v=mul(v,a);
	return v;
}
unsigned rev[N],A[N],B[N],C[N],E[N];
unsigned dft(unsigned*X){
	for(unsigned i=1;i<N;i<<=1){
		for(unsigned j=0;j<N;j+=i<<1){
			unsigned*f=X+j,*g=f+i,*e=E+i;
			for(unsigned k=0;k<i;++k){
				unsigned x=f[k],y=mul(g[k],e[k]);
				f[k]=fix1(x+y);
				g[k]=fix2(x-y);
			}
		}
	}
}
void cal(unsigned*a,int n,unsigned*A){
	for(int i=0;i<=n;++i)A[rev[i]]=a[i];
	dft(A);
}
void init(unsigned g){
	E[1]=1;
	for(int i=2;i<N;i<<=1){
		unsigned*e0=E+i/2,*e1=E+i,w=pw(g,(P-1)/i/2);
		for(int j=0;j<i;j+=2)e1[j]=e0[j>>1],e1[j+1]=mul(e1[j],w);
	}
}
void poly_multiply(unsigned*a,int n,unsigned*b,int m,unsigned*c){
	for(int i=1;i<N;++i)rev[i]=rev[i>>1]>>1|(i&1)<<20;
	init(G);
	cal(a,n,A);
	cal(b,m,B);
	init(pw(G,P-2));
	for(int i=0;i<N;++i)C[rev[i]]=mul(A[i],B[i]);
	dft(C);
	unsigned I=pw(N,P-2);
	for(int i=0;i<=n+m;++i)c[i]=mul(C[i],I);
}

评测结果