代码

#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[22];
cp a1[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:n>>1);
		if(rev[i]>i)
		{
			register cp tmp=a[i];
			a[i]=a[rev[i]];
			a[rev[i]]=tmp;
		}
	}
	for(register int i=2,s=1;i<=n;i<<=1,s++)
		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[s][k]);
				a[j+k]=plus(u,v);
				a[j+k+i/2]=minus(u,v);
			}
	if(t==-1)
		for(register int i=0;i<n;i++)
			a[i]=div(a[i],n);
}
void init()
{
	for(int i=1;i<=21;i++)
		w[i]=malloc((1<<(i-1))*16);
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{
}

评测结果