代码

#include<bits/stdc++.h>
#define maxn 3000005
#define Pi 3.1415926535897932384626433832795
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define db double
#define Ct const 
using namespace std;

char cb[1<<16],*cs=cb,*ct=cb;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<16,stdin),cs==ct)?0:*cs++)
template<class T>void read(T &res){char ch;
	for(;!isdigit(ch=getc()););
	for(res=ch-'0';isdigit(ch=getc());res=res*10+ch-'0');
}

struct cp{
	db r,i;cp(db r=0,db i=0):r(r),i(i){}
	cp operator +(Ct cp &B)Ct{ return cp(r+B.r,i+B.i); }
	cp operator -(Ct cp &B)Ct{ return cp(r-B.r,i-B.i); }
	cp operator *(Ct cp &B)Ct{ return cp(r*B.r-i*B.i,r*B.i+i*B.r);  }   
	cp conj()Ct{ return cp(r,-i); }
};

int Wl,lg[maxn],r[maxn];
cp W[maxn];
void init(int n){
	for(Wl=1;n>=2*Wl;Wl<<=1);
	rep(i,0,Wl) W[i]=cp(cos(i*Pi/Wl),sin(i*Pi/Wl));
	rep(i,2,Wl<<1) lg[i]=lg[i>>1]+1;
}
void FFT(cp *A,int n,int tp){
	rep(i,1,n-1) (i<(r[i]=(r[i>>1]>>1)|((i&1)<<(lg[n]-1))))&&(swap(A[i],A[r[i]]),0);cp t;
	for(int L=1,B=Wl;L<n;L<<=1,B>>=1) for(int s=0;s<n;s+=L<<1) for(int k=s,x=0;k<s+L;k++,x+=B) 
		t=(tp==1?W[x]:W[x].conj())*A[k+L],A[k+L]=A[k]-t,A[k]=A[k]+t;
	if(tp^1) rep(i,0,n-1) A[i].r/=n;
}
cp A[maxn],B[maxn];
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c){
	double x;
	rep(i,0,n) A[i].r=a[i];
	rep(i,0,m) A[i].i=b[i];
	init(n+m);
	FFT(A,Wl<<1,1);
	rep(i,0,(Wl<<1)-1) B[i]=(A[i]+A[i?(Wl<<1)-i:0].conj())*(A[i]-A[i?(Wl<<1)-i:0].conj())*cp(0,-0.25);
	FFT(B,Wl<<1,-1);
	rep(i,0,n+m) c[i]=round(B[i].r);
}

评测结果