代码

#include<math.h>

#define Maxord 2097152
#define ordn 2097512
#define sz 1000000
#define sz2 2000000

typedef struct Complex{double x,y;}Cpx;
inline Cpx pls(Cpx x,Cpx y){return(Cpx){x.x+y.x,x.y+y.y};}
inline Cpx mns(Cpx x,Cpx y){return(Cpx){x.x-y.x,x.y-y.y};}
inline Cpx mtp(Cpx x,Cpx y){return(Cpx){x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x};}
inline Cpx conj(Cpx v){return(Cpx){v.x,-v.y};}

inline void swap(Cpx*x,Cpx*y){Cpx z=*x;*x=*y;*y=z;}

void FFT(Cpx *A,int ord,int Flag){
	const double PI=acos(-1.0);
	for(int i=0,j=0;i<ord;++i){
		if(i>j)swap(A+i,A+j);
		for(int l=ord>>1;(j^=l)<l;l>>=1);
	}for(int i=1;i<ord;i<<=1){
		Cpx w;
		w.x=cos(PI/i);w.y=Flag*sin(PI/i);
		for(int j=0;j<ord;j+=i<<1){
			Cpx e,x,y;e.x=1,e.y=0;
			for(int k=0;k<i;++k,e=mtp(e,w)){
				x=A[j+k];y=mtp(A[j+k+i],e);
				A[j+k]=pls(x,y);A[j+k+i]=mns(x,y);
			}
		}
	}if(Flag==-1)
		for(int i=0;i<ord;++i)
			A[i].x/=ord;
}

Cpx A[Maxord+1],
	B[Maxord+1];

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c){
	for(int i=0;i<=sz;++i)
		A[i].x=a[i],A[i].y=b[i];
	for(int i=sz+1;i<=ordn;++i)
		A[i].x=A[i].y=0;

	Cpx o;
	o.x=0;o.y=-0.25;
	FFT(A,ordn,1);
	for(int i=0;i<ordn;++i)
		B[i]=mtp(mns(mtp(A[i],A[i]),conj(mtp(A[(ordn-1)&(ordn-i)],A[(ordn-1)&(ordn-i)]))),o);
	FFT(B,ordn,-1);

	for(int i=0;i<=sz2;++i)
		c[i]=B[i].x+0.5;
}

评测结果