代码

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef double du;
#ifndef M_PI
#define M_PI 3.1415926535897932384626433832795
#endif
struct cp{
	du x,y;
	cp(const du x=0,const du y=0):x(x),y(y){}
};
inline cp operator+(const cp&a,const cp&b){return cp(a.x+b.x,a.y+b.y);}
inline cp operator-(const cp&a,const cp&b){return cp(a.x-b.x,a.y-b.y);}
inline cp operator*(const cp&a,const cp&b){return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
int rev[1<<21],N;
cp*w[21];
void pre(int n){
	int i,j,k;
	for(N=1,k=0;N<=n;N<<=1)k++;
	for(i=0;i<N;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
	for(i=2,k=0;i<=N;i<<=1,k++){
		w[k]=new cp[i>>1];
		for(j=0;j<i>>1;j++)w[k][j]=cp(cos(j*M_PI/(i/2)),sin(j*M_PI/(i/2)));
	}
}
void fft(cp*a,int on){
	int i,j,k,f;
	cp t;
	for(i=0;i<N;i++){
		if(i<rev[i])swap(a[i],a[rev[i]]);
	}
	for(i=2,f=0;i<=N;i<<=1,f++){
		for(j=0;j<N;j+=i){
			for(k=0;k<i>>1;k++){
				t=w[f][k];
				t.y*=on;
				t=t*a[i/2+j+k];
				a[i/2+j+k]=a[j+k]-t;
				a[j+k]=a[j+k]+t;
			}
		}
	}
	if(on==-1){
		for(i=0;i<N;i++)a[i].y/=N;
	}
}
cp A[1<<21];
void poly_multiply(unsigned*a,int n,unsigned*b,int m,unsigned*c){
	int i;
	pre(n+m);
	for(i=0;i<=n;i++)A[i].x=a[i];
	for(i=0;i<=m;i++)A[i].y=b[i];
	fft(A,1);
	for(i=0;i<N;i++)A[i]=A[i]*A[i];
	fft(A,-1);
	for(i=0;i<=n+m;i++)c[i]=llround(A[i].y*.5);
}

评测结果