首页 > 代码库 > 【FFT】专题总结
【FFT】专题总结
学了若干天终于学(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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。