代码

#include<math.h>

typedef double db;
typedef struct
{
	db x,y;
} cp;
cp plus(register cp a,register cp b)
{
	register cp c;
	c.x=a.x+b.x;
	c.y=a.y+b.y;
	return c;
}
cp minus(register cp a,register cp b)
{
	register cp c;
	c.x=a.x-b.x;
	c.y=a.y-b.y;
	return c;
}
cp mul(register cp a,register cp b)
{
	register cp c;
	c.x=a.x*b.x-a.y*b.y;
	c.y=a.x*b.y+a.y*b.x;
	return c;
}
cp div(register cp a,register int b)
{
	register cp c;
	c.x=a.x/b;
	c.y=a.y/b;
	return c;
}

cp w[1<<20];
cp a[1<<21];
int rev[1<<21];
void fft(cp *a,register int n,int t)
{
	for(register int i=1;i<n;i++)
	{
		rev[i]=(rev[i>>1]>>1)|(i&1?n>>1:0);
		if(rev[i]>i)
		{
			register cp tmp=a[i];
			a[i]=a[rev[i]];
			a[rev[i]]=tmp;
		}
	}
	for(register int i=2;i<=n;i<<=1)
		for(register int j=0;j<n;j+=i)
			for(register int k=0;k<i/2;k++)
			{
				register cp u=a[j+k];
				register cp v=mul(a[j+k+i/2],w[(1<<21)/i*k]);
				a[j+k]=plus(u,v);
				a[j+k+i/2]=minus(u,v);
			}
	if(t==-1)
	{
		for(register int i=1,j=n-1;i<j;i++,j--)
		{
			cp tmp=a[j];
			a[j]=a[i];
			a[i]=tmp;
		}
		for(register int i=0;i<n;i++)
			a[i]=div(a[i],n);
	}
}
void init()
{
	cp s;
	db pi=acos(-1);
	s.x=cos(2*pi/(1<<21));
	s.y=sin(2*pi/(1<<21));
	w[0].x=1;
	w[0].y=0;
	for(int i=1;i<1<<20;i++)
		w[i]=mul(w[i-1],s);
}
void poly_multiply(unsigned *a1,register int n,register unsigned *a2,register int m, unsigned *a3)
{
	init();
	int k=1<<21;
	for(register int i=0;i<k;i++)
		a[i].x=a[i].y=0;
	for(register int i=0;i<=n;i++)
		a[i].x=a1[i];
	for(register int i=0;i<=m;i++)
		a[i].y=a2[i];
	fft(a,k,1);
	for(register int i=0;i<k;i++)
		a[i]=mul(a[i],a[i]);
	fft(a,k,-1);
	for(register int i=0;i<=n+m;i++)
		a3[i]=(a[i].y/2+0.5);
}

评测结果