37D
#include<bits/stdc++.h>
#include<cstdio>
#include<math>
define maxn 100009
double epsilon[maxn],temp[maxn];
int void init_epsilon(int n)
{
double pi=acos(-1);
for(int i=1;i!=n;++i)
{
epsilon[i]=(double)(cos(2.0*pi*i/n),sin(2.0*pi*i/n));
arti_epsilon[i]=conj(epsilon[i]);
}
}
void fft(int n,double *buffer,int offset,int step,double* epsilon)
{
if(n==1) return ;
int m=n>>1;
fft(m,buffer,offset,step<<1,epsilon);
fft(m,buffer,offset+step,step<<1,epsilon);
for(int k=0;k!=m;k++)
{
int pos=2*step*k;
temp[k]=buffer[pos+step]+epsilon[k*step]*buffer[pos+offset+step];
temp[k]=buffer[pos+step]-epsilon[k*step]*buffer[pos+offset+step];
}
for(int i=0;i!=n;++i)
buffer[i*step*offset]=temp[i];
}
int main()
{
}
评论