代码

#include <math.h>
using namespace std;
#define ui unsigned int
const ui N=262200;
const double Pi=acos(-1);
ui l,p,R[N];
struct Comp{
	double r,i;
	Comp():r(0),i(0){}
	Comp(double R):r(R),i(0){}
	Comp(double R,double I):r(R),i(I){}
	Comp conj(){return Comp(r,-i);}
	friend Comp operator + (const Comp &a,const Comp &b){
		return (Comp){a.r+b.r,a.i+b.i};
	}
	friend Comp operator - (const Comp &a,const Comp &b){
		return (Comp){a.r-b.r,a.i-b.i};
	}
	friend Comp operator * (const Comp &a,const Comp &b){
		return (Comp){a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r};
	}
}A[N],B[N],T[N],w[N];
void work(Comp *A,ui f){
	for(ui i=0;i<l;i++)T[i]=A[R[i]];
	for(ui i=0;i<l;i++)A[i]=T[i];
	Comp W,t0,t1;
	for(ui i=1;i<l;i<<=1){
		W=Comp(cos(Pi/i),f*sin(Pi/i));
		w[0]=1;
		for(ui j=1;j<i;j++)w[j]=w[j-1]*W;
		for(ui j=0;j<l;j+=i<<1)
			for(ui k=0;k<i;k++){
				t0=A[j+k],t1=A[i+j+k];
				A[j+k]=t0+t1*w[k],A[i+j+k]=t0-t1*w[k];
			}
	}
}
void poly_multiply(ui *a,ui n,ui *b,ui m,ui *c){
	Comp t0,t1;
	l=1,p=0;
	while(l<n+m-1)l<<=1,p++;
	for(ui i=1;i<l;i<<=1)
		for(ui j=0;j<i;j++)R[i+j]=R[j]+l/i/2;
	for(ui i=0;i<n;i++)A[i].r=a[i];
	for(ui i=0;i<m;i++)A[i].i=b[i];
	work(A,1);
	for(ui i=0;i<l;i++)B[i]=A[(l-i)%l].conj();
	for(ui i=0;i<l;i++){
		t0=A[i],t1=B[i];
		A[i]=(t0+t1)*Comp(0.5,0),B[i]=(t0-t1)*Comp(0,-0.5);
		A[i]=A[i]*B[i];
	}
	work(A,-1);
	for(ui i=0;i<l;i++)c[i]+=(long long)(A[i].r/l+0.5);
}

评测结果