FFT，快速傅里叶变换。听说是一个可以在nlogn的复杂度内解决多项式乘法的东西，就是求类似于c[k]=sigma(a[i]*b[k-i])这样的式子，听说这样的式子叫卷积。
迪克李教导我们只要大概知道他在干什么和大致的原理就可以喽，然后就把代码背下来就可以了。听说这很兹磁。
那么既然背代码，当然要挑好的背。听说迪克李给了我们策爷的模板。
struct cp{double x,y;};//这定义的是一个复数的形式，x表示实数部分系数，y表示虚数部分系数
cp a[N],b[N],cur[N];
cp operator *(cp x,cp y){return (cp){x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x};}
cp operator +(cp x,cp y){return (cp){x.x+y.x,x.y+y.y};}
cp operator -(cp x,cp y){return (cp){x.x-y.x,x.y-y.y};}
void fft(cp *a,int n,int fl)//fl=1/-1,1表示把系数转成点对，-1表示把点对转成系数
{
for(int i=n>>1,j=1;j<n;j++)
{
if (i<j) swap(a[i],a[j]);
int k=n>>1;
for (;k&i;i^=k,k>>=1);i^=k;
}
for(int m=2;m<=n;m<<=1)
{
cp w=(cp){cos(2*pi*fl/m),sin(2*pi*fl/m)};
cur[0]=(cp){1,0};
for (int i=1;i<m;i++) cur[i]=cur[i-1]*w;
for (int i=0;i<n;i+=m)
for (int j=i;j<i+(m>>1);++j)
{
cp u=a[j],v=a[j+(m>>1)]*cur[j-i];
a[j]=u+v;
a[j+(m>>1)]=u-v;
}
}
}
评论 (0)
