FFT的小板子问题解析

FFT 快速傅里叶变换 丢个带注释的板子先
(其实是不会蝶形变换&复数意义 虽然搞不懂也没关系辣)

Code

#pragma GCC optimize(2) 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define oo 2139062143
#define fo(i,x,y) for (ll i=(x);i<=(y);++i)
using namespace std;
typedef double db;
typedef long long ll;
typedef complex com;
const ll N=524288+10;
const db pi=acos(-1);//cos 180=-1
com v[2][N],w[N]/*单位根*/;
ll ans[N];
ll n,wz[N],m;
void init(ll x)
{
 for (m=1;m>1]>>1)+((i&1)*(m>>1));
 w[0]=1,w[1]=com(cos(pi*2.0/m),sin(pi*2.0/m));
 fo(i,2,m) w[i]=w[i-1]*w[1]; 
}
com a[N]; 
void dft(com *c)
{
 fo(i,0,m-1) a[wz[i]]=c[i];com tp; 
 for (ll wh=2,hf=1;wh<=m;hf=wh,wh<<=1)
 fo(i,0,hf-1) for (ll l=i;l>1) swap(v[0][i],v[0][m-i]);//用来代替求W[1]的-1 
  dft(v[0]);
 fo(i,n-1,2*n-2) printf("%lf\n",v[0][i].real()/(1.0*m));
 return 0;
}