本文共 1219 字，大约阅读时间需要 4 分钟。

快速傅里叶变换（FFT）详解

　　（这是我第一次写博，不喜勿喷...）

　　关于FFT已经听闻已久了，这次终于有机会在Function2的介绍下来了解一下FFT了。

　　快速傅里叶变换(Fast Fourier Transformation)简称FFT。在各大OI竞赛中也常有用到，也是一个十分优秀的可以装逼的好算法

　　在这篇blog中，有大量数学推导，因为我懒得写公式（好复杂，逃），所以用图片代替了╮(╯▽╰)╭，如有不适，望见谅（逃~~）。

 基础知识：

多项式的度数：

多项式的线性空间

系数表达

向量的卷积

分治乘法（如果你急着和MM约会或机房要关门了，那跳过也无妨）

点值表达

插值

点值计算分析

 单位复数根

单位复数根的性质

1. 消去引理

　　2.折半引理

　　3.求和引理

铺垫都铺完了，让我们一起进入DFT,FFT,IDFT的美妙世界吧！

离散傅里叶变换（Discrete Fourier Transform 简称DFT）

 快速傅里叶变换（FFT）（终于等到你~~）

逆离散傅里叶变换（Inverse Discrete Fourier Transform 简称IDFT）

 FFT的迭代实现

我们类似于需要像这样实现FFT：

知识点终于讲完了，接下来我们就要开始写板子了

板子题：

代码附上~~

1 #include
   
     2 #include
    
      3 #include
     
       4 #include
      
        5 #include
       
         6 #include
        
          7 using namespace std; 8 const int mod=1e9+7; 9 const double pi=acos(-1);10 struct cn11 {12 double x,y;13 cn (double x=0,double y=0):x(x),y(y) {}14 }a[300005],b[300005],c[300005];15 cn operator + (const cn &a,const cn &b) {return cn(a.x+b.x,a.y+b.y);}16 cn operator - (const cn &a,const cn &b) {return cn(a.x-b.x,a.y-b.y);}17 cn operator * (const cn &a,const cn &b) {return cn(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}18 void fft(cn a[],int n,int l,int f) 19 { 20 int rev[n+5];21 rev[0]=0;22 for (int i=1; i
         
          >1]>>1)|((i&1)<
         
        
       
      
     
    
   

转载地址：http://mrows.baihongyu.com/