代码

#define $(x) mul(x,RR)
const unsigned N=2097152,G=3;
const unsigned P=479<<21|1,I2=(P+1)/2,R=1<<30,R1=R-1,iP=1004535807,RR=473382811,iR=939790336;
inline unsigned fix1(unsigned x){return x>=P?x-P:x;}
inline unsigned fix2(int x){return x<0?x+P:x;}
typedef unsigned long long u64;
inline unsigned mul(unsigned a,unsigned b){
	u64 ab=u64(a)*b;
	return fix1((ab+(ab*iP&R1)*P)>>30);
}
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);
			}
		}
	}
}
unsigned rs[10];
void cal(unsigned*a,int n,unsigned*A){
	for(int i=0;i<=n;++i)A[rev[i]]=rs[a[i]];
	dft(A);
}
void init(unsigned g){
	E[1]=rs[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=0;i<10;++i)rs[i]=$(i);
	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=mul(pw($(N),P-2),1);
	for(int i=0;i<=n+m;++i)c[i]=mul(C[i],I);
}

评测结果