#include <cstdio>
#include <cstdlib>
#include <cmath>
const double pi=acos(-1);
struct complex
{
	double real,imag;
	complex(double a=0,double b=0){real=a;imag=b;}
};
complex operator + (const complex& t1,const complex& t2)
{return complex(t1.real+t2.real,t1.imag+t2.imag);}
complex operator - (const complex& t1,const complex& t2)
{return complex(t1.real-t2.real,t1.imag-t2.imag);}
complex operator * (const complex& t1,const complex& t2)
{return complex(t1.real*t2.real-t1.imag*t2.imag,t1.real*t2.imag+t1.imag*t2.real);}
inline int reverse(int v,int n)
{
	int ans=0;
	for(int i=0;i<n;i++)
		ans+=(1<<i)*(v>>(n-i-1)&1);
	return ans;
}
void fft(complex target[],const complex from[],int n,int rev)
{
	int len=1<<n;
	for(int i=0;i<len;i++)target[i]=from[reverse(i,n)];
	for(int i=1;i<=n;i++)
	{
		int d=1<<i;
		complex wn=complex(cos(2*pi/d*rev),sin(2*pi/d*rev));
		for(int j=0;j<len;j+=d)
		{
			complex w=complex(1,0);
			for(int k=j;k<j+d/2;k++)
			{
				complex t=target[k],p=target[k+d/2]*w;
				target[k]=t+p;target[k+d/2]=t-p;
				w=w*wn;
			}
		}
	}
	if(rev==-1)
		for(int i=0;i<len;i++)
			target[i].real/=len;
}

FFT有各种神奇的用法

还可以分块呢呢呢呢呢呢呢呢呢呢