首页 > 代码库 > 【FFT】专题总结

【FFT】专题总结

2024-07-04 23:47:34   229人阅读

学了若干天终于学(bei)会了传说中的法法塔

感觉也没那么难用嘛

 

fft快速傅里叶变换 在大表课件上写就是解决高精乘的工具 其实很有理有据

fft就是用复数的折半引理优化两个多项式相乘的高端东西

他能使O(n^2)的多项式相乘优化到O(nlogn)

听ak说这也是比较模板的东西 也就不去理解什么证明了（其实是我看了半天看不懂TAT）

 

贴个代码吧（史上最短总结233- -）

 1 int bit_rev(int t,int n){
 2     int res=0;
 3     for (int i=0;i<n;i++) res|=(t>>(n-i-1)&1)<<i;
 4     return res;
 5 }
 6 void fft(cd *a,int n,int rev){
 7     int len=1<<n;
 8     static cd y[N*4];
 9     for (int i=0;i<len;i++) y[i]=a[bit_rev(i,n)];
10     for (int d=1;d<len;d<<=1){
11         cd wn=exp(cd(0,PI*rev/d));
12         for (int k=0;k<len;k+=(d<<1)){
13             cd w=cd(1,0);
14             for (int i=k;i<k+d;i++,w*=wn){
15                 cd u=y[i],v=w*y[i+d];
16                 y[i]=u+v;
17                 y[i+d]=u-v;
18             }
19         }
20     }
21     if (rev==-1)
22     for (int i=0;i<len;i++) y[i]/=len;
23     for (int i=0;i<len;i++) a[i]=y[i];
24 }
25 void mul(int *a,int la,int *b,int lb,int *c,int &lc){
26     int len=1,n=0;
27     static cd t1[N*4],t2[N*4];
28     for (;len<la*2 || len<lb*2;len<<=1,++n);
29     for (int i=0;i<len;i++){
30         t1[i]=cd(i<la ? a[i] : 0,0);
31         t2[i]=cd(i<lb ? b[i] : 0,0);
32     }
33     fft(t1,n,1);
34     fft(t2,n,1);
35     for (int i=0;i<len;i++) t1[i]*=t2[i];
36     fft(t1,n,-1);
37     lc=len-1;
38     for (int i=0;i<len;i++) c[i]=(int)(t1[i].real()+0.5);
39 }

 


联系
我们