FFT学习笔记

FFT(Fast Fourier Transform)

快速傅里叶变换

---

引入

• 百度一下

这里的很多的工程上的文章和学术性的文章都是以音频和图像的处理和生活中的实际用途还有纯数学角度讲的，但是作为一个OIer，我们一般是不会用到这些的，所以这里就不讲解什么时域频域转换和波的分析之类的东西，而是将如何在OI中应用。

概念与前置

人物了解

• 傅里叶

其实这里要讲的傅里叶变换和完整的傅里叶变换有一定的区别，我们下面来看看傅里叶变换的两个公式:

• 傅里叶变换
  

  F(ω)=F[f(t)]=∫−∞∞f(t)e−iωtdt$$F(\omega )=\mathcal{F}[f(t)]=\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}f(t)e^{-i\omega t}dt$$

• 傅里叶逆变换
  

  f(t)=F−1[F(ω)]=12π∫−∞∞F(ω)eiωtdω$$f(t)={\mathcal{F}}^{-1}[F(\omega )]=\frac{1}{2\pi }\underset{-\mathrm{\infty }}{\overset{\mathrm{\infty }}{\int }}F(\omega )e^{i\omega t}d\omega$$

其中的F$\mathcal{F}$代表傅里叶变换，F−1${\mathcal{F}}^{-1}$表示傅里叶逆变换。

下面扯一些和算法并无多大联系的知识。

如果不想看直接可以调到下一个标题

这两个变换公式中，f(t)$f(t)$为以t$t$为周期的周期函数，且t$t$还满足狄利赫里条件。

狄利赫里条件
内容概括:也就是在给定的周期函数在有限的区间内,只有有限个第一类间断点和有限个极大值和极小值。满足该条件就符合傅里叶级数收敛。

感觉每次学啥都是递归似的学习啊QWQ

傅里叶级数
内容概括:任何周期函数都可以用正弦函数和余弦函数构成的无穷级数来表示（选择正弦函数与余弦函数作为基函数是因为它们是正交的），后世称傅里叶级数为一种特殊的三角级数，根据欧拉公式，三角函数又能化成指数形式，也称傅立叶级数为一种指数级数。

• 傅里叶级数的收敛

设f$f$是周期为2π$2\pi$且在[−π,π]$[-\pi ,\pi ]$上的可积或绝对可积的函数，如果f$f$在x0$x_0$处存在倒数f′(x0)$f^{{}^{\prime }}(x_0)$，或是有两个有限的单侧倒数:

f′+(x0)=limt→0+f(x0+t)−f(x0)t$$f_{+}^{{}^{\prime }}(x_0)=\underset{t\to 0^{+}}{lim}\frac{f(x_0+t)-f(x_0)}{t}$$

f′−(x0)=limt→0+f(x0−t)−f(x0)−t$$f_{-}^{{}^{\prime }}(x_0)=\underset{t\to 0^{+}}{lim}\frac{f(x_0-t)-f(x_0)}{-t}$$

那么f$f$的Fourier$\mathrm{F}\mathrm{o}\mathrm{u}\mathrm{r}\mathrm{i}\mathrm{e}\mathrm{r}$级数在x0$x_0$处收敛于f(x0)$f(x_0)$，如果f$f$在x0$x_0$处仅有两个有限的广义单侧导数:

limt→0+f(xo+t)−f(x0+0)t$$\underset{t\to 0^{+}}{lim}\frac{f(x_o+t)-f(x_0+0)}{t}$$

limt→0+f(x0−t)−f(x0−0)−t$$\underset{t\to 0^{+}}{lim}\frac{f(x_0-t)-f(x_0-0)}{-t}$$

那么f$f$的Fourier$\mathrm{F}\mathrm{o}\mathrm{u}\mathrm{r}\mathrm{i}\mathrm{e}\mathrm{r}$级数在x0$x_0$处收敛于12(f(x0+0)+f(x0−0))$\frac{1}{2}(f(x_0+0)+f(x_0-0))$.

参考文章

傅里叶级数的三角式:

f(t)=a0+∑n=1∞(ancos(nωt)+bnsin(nωt))$$f(t)=a_0+\sum _{n=1}^{\mathrm{\infty }}(a_n\cos (n\omega t)+b_n\sin (n\omega t))$$

其中ω=2πT$\omega =\frac{2\pi }{T}$，T$T$为函数周期。an$a_n$和bn$b_n$分别控制了正弦波的振幅与频率。说好的不讲这些的呢？

它还可以用复指数形式和积分形式来表示:

f(t)=∑n=−∞∞Fneinωt$$f(t)=\sum _{n=-\mathrm{\infty }}^{\mathrm{\infty }}{F}_n{e}^{in\omega t}$$

Fn=1T∫T0f(t)e−inωtdt$$F_n=\frac{1}{T}{\int }_0^{T}f(t)e^{-in\omega t}dt$$

其中的F$F$就是周期函数f$f$的傅里叶级数(Fourier Series, FS)

---

再回到傅里叶变换的两个式子，里面的F(ω)$F(\omega )$称为f(t)$f(t)$的象函数，而f(t)$f(t)$被称为F(ω)$F(\omega )$的原象函数。

象函数与原象函数
拉普拉斯变换
内容概述:这是一种线性的积分变换，可以将一个有参数实数t(t≥0)$t(t\ge 0)$的函数变换成一个参数为复数的函数S$S$。
在拉普拉斯变换中对于f(t)$f(t)$的双边拉普拉斯变换F(s)$F(s)$,我们称其中的F(ω)$F(\omega )$为f(t)$f(t)$的象函数，而f(t)$f(t)$则为F(ω)$F(\omega )$的原象函数。

---

跳出递归

下面开始由最简单的入手一步步讲解FFT$\mathrm{F}\mathrm{F}\mathrm{T}$

多项式

• 定义

这个应该来看的人都知道吧

我们把形如a0+a1x+a2x2+⋯+an−1xn−1$a_0+a_{1}x+a_2{x}^2+\cdots +a_{n-1}{x}^{n-1}$的式子称作多项式(其中a0$a_0$可以形式化的写作a0x0$a_0{x}^0$)。
其中的a0$a_0$~a1$a_1$叫做多项式的系数，我们将一个关于x$x$的多项式可以简记为A(x)$A(x)$。

多项式的通式表达:

A(x)=∑i=0n−1aixi$$A(x)=\sum _{i=0}^{n-1}{a}_i{x}^i$$

一些规定:

• 我们令n$n$为一个多项式的次数界，即次数范围，那么这个多项式中的任意一项的次数都要小于n$n$。

• 我们定义两个多项式的加减法如下(两个多项式加起来的次数界去较大的一个):
  

  A(x)±B(x)=∑i=0n−1(ai±bi)xi$$A(x)\pm B(x)=\sum _{i=0}^{n-1}(a_i\pm b_i)x^i$$

这个可以O(n)$O(n)$的简单计算啦。

• 我们接下来定义两个多项式的卷积(好像也就是乘法吧):

A(x)⨂B(x)=∑i=0An−1∑j=0Bn−1aibi⋅xi×j$$A(x)⨂B(x)=\sum _{i=0}^{A_n-1}\sum _{j=0}^{B_n-1}{a}_i{b}_i\cdot x^{i\times j}$$

两个多项式的卷积的次数界为(An+Bn)$(A_n+B_n)$。

卷积式子也可以写成以下形式:

A(x)⨂B(x)=∑i=0n−1(∑j=0iajbi−j)xi$$A(x)⨂B(x)=\sum _{i=0}^{n-1}\left(\sum _{j=0}^i{a}_j{b}_{i-j}\right)x^i$$

那么从定义式的角度来看，朴素的算法只能O(n2)$O(n^2)$的计算，那么有没有更快一点的计算呢?我们接着看。

---

多项式的表达方法

• 第一种:系数表达法

也就是我们上面的定义中的方法，用一组系数a0$a_0$~a1$a_1$来表示一个多项式，我们可以将这个系数看作一个n−1$n-1$维的向量，记作a→=(a0,a1,⋯,an−1)$a^{\to }=(a_0,a_1,\cdots ,a_n-1)$ ,然后向量一般可以与矩阵联系起来(后面有用)。

• 第二种:点值表达法

因为一个多项式A(x)$A(x)$的实质是关于x$x$的一个函数，而一个n−1$n-1$次的函数可以由n$n$个点对(x,y)$(x,y)$确定其形式形态，所以我们可以运用这个性质来表示一个多项式。对于一个次数界为n−1$n-1$的多项式，我们可以选取n$n$个x$x$，记作(x0,x1,⋯,xn−1)$(x_0,x_1,\cdots ,x_{n-1})$，然后带入这个多项式，可以对应求出n$n$个y$y$，我们把它记作(y0,y1,⋯,yn−1)$(y_0,y_1,\cdots ,y_{n-1})$，那么现在我们就得到了这个函数(多项式)上的n$n$个点对，我们就可以用这n$n$个点对(xi,yi)$(x_i,y_i)$来表示这个多项式。其实这也是离散化的表示一个函数(多项式)的方法。

然后我们将其形式化:

令α={(xi,yi)[yi=A(xi)]|i∈[0,n−1],i∈Z}$\alpha =\{(x_i,y_i)[y_i=A(x_i)]|i\in [0,n-1],i\in Z\}$
这个α$\alpha$即为A(x)$A(x)$的点值表达式。

我们用这个点值表达式有什么用处呢?
点值表达式的方便之处在于我们将两个多项式相乘如果用系数表达式则是O(n2)$O(n^2)$的，而使用点值表达式，则只用把两个多项式对应xi$x_i$的点相乘即可，即变为O(n)$O(n)$的了。(这里的点相乘会用到复数的知识)。

复数

复数其实就是一种数域的扩展，为了解决一些实数解决不了的和平面几何等的问题。

• 百度一下

• 有关复数的运算

于是上面的点便可以定义为复数域C$C$上的复数。
那么对于一个点p$p$，我们可以将其表示为p=x+yi$p=x+yi$，其中i$i$就是复数单位，其中i$i$满足i2=−1$i^2=-1$。

那么这个点的四则运算就可以定义如下(结合复数的运算):

对于两个点p,q$p,q$，其中p=xp+ypi,q=xq+yqi$p=x_p+y_{p}i,q=x_q+y_{q}i$，我们可以用(xp,yp)$(x_p,y_p)$来表示点p$p$。

• 加法+$+$
  

  p+q=(xp+xq,yp+yq)$$p+q=(x_p+x_q,y_p+y_q)$$

• 减法−$-$
  

  p−q=(xp−xq,yp−yq)$$p-q=(x_p-x_q,y_p-y_q)$$

• 乘法×$\times$
  

  p×q=(xp×xq−yp×yq,xp×yq+xq×yp)$$p\times q=(x_p\times x_q-y_p\times y_q,x_p\times y_q+x_q\times y_p)$$

• 除法÷$÷$
  

  pq=(xp×xq+yp×yqx2q+y2q,yp×xq−yq×xpx2q+y2q)$$\frac{p}{q}=\left(\frac{x_p\times x_q+y_p\times y_q}{x_q^2+y_q^2},\frac{y_p\times x_q-y_q\times x_p}{x_q^2+y_q^2}\right)$$

• 共轭复数conj$conj$【百度百科】
  conj(p)=(xp,−yp)$conj(p)=(x_p,-y_p)$

复数就介绍到这，我们的点值表达式中的点的运算就是如此（把点用复数表示了（复平面））。

---

多项式求值

那么我们对于一个xi$x_i$如何快速求出A(x)$A(x)$呢?
会的大佬可以跳过 Orz

先观察定义式（次数界为n$n$）:

A(x)=∑i=0n−1aixi$$A(x)=\sum _{i=0}^{n-1}{a}_i{x}^i$$

最笨的方法O(n2)$O(n^2)$，每次暴力计算xi$x^i$。
优化一点就是O(nlog2n)$O(nlo{g}_{2}n)$,利用快速幂。
再好一点的就是O(n)$O(n)$预处理xi$x^i$,然后O(n)$O(n)$计算。

那么有没有极致一点的直接O(n)$O(n)$的方法呢？

我们就是用秦九韶算法(Horner法则)。
其实他的本质类似于分治递归处理。

我们将这个多项式展开:

A(x)=a0+a1x+a2x2+a3x3+⋯+an−1xn−1$$A(x)=a_0+a_{1}x+a_2{x}^2+a_3{x}^3+\cdots +a_{n-1}{x}^{n-1}$$

每次提取一个x$x$，然后一直这么做下去，就得到如下变换。

a0+x⋅(a1+a2x+a3x2+⋯+an−1xn−2)$$a_0+x\cdot (a_1+a_{2}x+a_3{x}^2+\cdots +a_{n-1}{x}^{n-2})$$

a0+x⋅(a1+x⋅(a2+a3x+⋯+an−1xn−3))$$a_0+x\cdot (a_1+x\cdot (a_2+a_{3}x+\cdots +a_{n-1}{x}^{n-3}))$$

⋯$$\cdots$$

的到最里面一层就是

⋯(an−2+an−1x)$$\cdots (a_{n-2}+a_{n-1}x)$$

我们发现变成了一个一次的式子，那么将xi$x_i$带入，求出值为v0$v_0$，继续得到如下式子:

⋯(an−3+v0x)$$\cdots (a_{n-3}+v_{0}x)$$

然后同样计算，直到最后一个，那么每次都是一个一次的式子，O(1)$O(1)$的计算，然后总的复杂度就是O(n)$O(n)$啦。

代码实现就很简单啦

int v=a[n-1];
for(int i=n-2;i>=0;i--){
    v=v*x+a[i];
}

small trick$\mathcal{s}\mathcal{m}\mathcal{a}\mathcal{l}\mathcal{l}\mathcal{t}\mathcal{r}\mathcal{i}\mathcal{c}\mathcal{k}$

---

接下来我们就继续看多项式卷积，我们有如下卷积式子:

C(x)=A(x)⨂B(x)=∑i=0An−1∑j=0Bn−1aibi⋅xi×j$$C(x)=A(x)⨂B(x)=\sum _{i=0}^{A_n-1}\sum _{j=0}^{B_n-1}{a}_i{b}_i\cdot x^{i\times j}$$

表示为点值表达式就有C(x)={xi,A(xi)⋅B(xi)|i∈[0,n−1],i∈Z}$C(x)=\{x_i,A(x_i)\cdot B(x_i)|i\in [0,n-1],i\in Z\}$

我们发现这样可以O(n)$O(n)$的计算(前面的点值表达方式说过)。

但虽然计算过程中复杂度十分优秀，但是预处理呢?

我们一般是得到一个系数表达式，然后转换为点值表达式的朴素复杂度为O(n2)$O(n^2)$，先枚举n$n$个xi$x_i$，然后每次O(n)$O(n)$的计算多项式的值。然后我们O(n)$O(n)$的运算，但大多数时候最终的答案要为系数表达式，所以最朴素的转变回来的方式就是O(n3)$O(n^3)$高斯消元(也就是解一个知道n$n$个点的n$n$次方程)。

这个，，，，还不如暴力呢，emmmm。

那么有没有一种快速的变换来解决这种预处理，当然有啦，那就是——————————-> FFT

---

继续前置⋯⋯$\cdots \cdots$

插值-点值转换

我们继续定义一种对于多项式的运算，名叫DFT(A(x))$DFT(A(x))$（其实有的读者就应该知道这就是 离散傅里叶变换discrete Fourier transform$discreteFouriertransform$）

它的作用就是将系数表达式的A(x)$A(x)$转换为点值表达式。

而我们同样的还要定义它的逆运算，为IDFT(A(x))$IDFT(A(x))$，作用为将一个点值表达式转换为系数表达式的转换。

那么多项式的卷积就可以如下计算：

• DFT(A(x))$DFT(A(x))$ DFT(B(x))$DFT(B(x))$

• C(x)=∑n−1i=0A(xi)⋅B(xi)$C(x)=\sum _{i=0}^{n-1}A(x_i)\cdot B(x_i)$

• IDFT(C(x))$IDFT(C(x))$

最后的答案就为C(x)$C(x)$了。

但是如何快速进行DFT$DFT$与IDFT$IDFT$呢？肯定不能用朴素的方法。

所以这里就要运用复数的神奇性质啦!

---

单位根

一种十分神奇且超级特殊的一类方程的根。

定义: 即对于满足方程xn=1$x^n=1$的x$x$，被称为n$n$次单位根。

但从表面来看，n$n$为奇数时x$x$只有1，偶数时有−1,1$-1,1$，这样的根太少，且用处不大，那么我们就将目光投向复数。

重要的性质 : i2=−1$i^2=-1$,i3=−i$i^3=-i$,i4=1,⋯$i^4=1,\cdots$

那么在复数上，xn=1$x^n=1$就几乎有无数多组解，那么这些解就被称为n$n$次单位复数根。

因为有着xn=1$x^n=1$的性质，那么将其带入多项式，所有的xi$x^i$都可以变为1，那不就好解多啦。

如何求得复数意义下xn=1$x^n=1$的解呢？

• 欧拉公式

exi=cosx+isinx$e^{xi}=\cos x+i\sin x$

其中一个特殊的性质：(cosx+isinx)k=coskx+isinkx$(\cos x+i\sin x{)}^k=\cos kx+i\sin kx$
证明：用三角恒等式，变形，然后推出k$k$在奇数和偶数时的通式证明即可。

那么欧拉公式如何得到的呢？

证明：
通过Taylor$Taylor$展开得到（有高数基础的应该知道，不知道的也可以百度）：

ex=1+x+x22!+⋯+xnn!+⋯$$e^x=1+x+\frac{x^2}{2!}+\cdots +\frac{x^n}{n!}+\cdots$$

cosx=1−x22!+x44!−x66!+⋯$$\cos x=1-\frac{x^2}{2!}+\frac{x^4}{4!}-\frac{x^6}{6!}+\cdots$$

sinx=x−x33!+x55!−x77!+⋯$$\sin x=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots$$

然后我们将其扩展到复数域上，由于i=−1−−−√$i=\sqrt{-1}$

所以可以得到如下式子：

exi=1+xi−x22!−x33!i+x44!+x55!i−⋯$$e^{xi}=1+xi-\frac{x^2}{2!}-\frac{x^3}{3!}i+\frac{x^4}{4!}+\frac{x^5}{5!}i-\cdots$$

变形得到：

=(1−x22!+x44!−⋯)+i⋅(x−x33!+x55!−⋯)$$=\left(1-\frac{x^2}{2!}+\frac{x^4}{4!}-\cdots \right)+i\cdot \left(x-\frac{x^3}{3!}+\frac{x^5}{5!}-\cdots \right)$$

=cosx+isinx$$=\cos x+i\sin x$$

于是得到证明。

如果我们将x$x$用π$\pi$来代替，就可以得到

eiπ=cosπ+isinπ=−1+i×0=−1$$e^{i\pi }=\cos \pi +i\sin \pi =-1+i\times 0=-1$$

即一个神奇的公式就是eiπ+1=0$e^{i\pi }+1=0$

然后我们接着将x=2⋅kπ(k∈Z)$x=2\cdot k\pi (k\in Z)$
那么又能够得到e2⋅kπi=1$e^{2\cdot k\pi i}=1$，那么这里的e2⋅kπi$e^{2\cdot k\pi i}$不就正好符合我们的方程xn=1$x^n=1$吗？
然后我们令x=e2kπin(k∈Z)$x=e^{\frac{2k\pi i}{n}}(k\in Z)$，然后我们记ωkn=x${\omega }_n^k=x$,那么这个就是一个n$n$次单位复数根。
而且可以证明这样的n$n$次单位复数根一定有n$n$个：
证明：
令k=nr+p,p∈[0,n−1]$k=nr+p,p\in [0,n-1]$，则ωkn=e2kπin=e2(nr+p)πin=e2nrπin+2pπin=e2nrπin×e2pπin=1r×e2pπin=e2pπin${\omega }_n^k=e^{\frac{2k\pi i}{n}}=e^{\frac{2(nr+p)\pi i}{n}}=e^{\frac{2nr\pi i}{n}+\frac{2p\pi i}{n}}=e^{\frac{2nr\pi i}{n}}\times e^{\frac{2p\pi i}{n}}=1^r\times e^{\frac{2p\pi i}{n}}=e^{\frac{2p\pi i}{n}}$
有因为p$p$有n$n$个，那么这个根也就有n$n$个。

记这些根为ω0n${\omega }_n^0$~ωn−1n${\omega }_n^{n-1}$,且它们在乘法意义下构成一个群，即满足ωinωjn=ωi+jn=ω(i+j)modnn${\omega }_n^i{\omega }_n^j={\omega }_n^{i+j}={\omega }_n^{(i+j)\mathrm{mod}n}$。

还有一个特殊的性质是ω−1n=ωn−1n${\omega }_n^{-1}={\omega }_n^{n-1}$
证明:

ω−1n=1×ω−1n=e2πi×e−2πin=e2πi−2πin=e2(n−1)πin=ωn−1n$${\omega }_n^{-1}=1\times {\omega }_n^{-1}=e^{2\pi i}\times e^{\frac{-2\pi i}{n}}=e^{2\pi i-\frac{2\pi i}{n}}=e^{\frac{2(n-1)\pi i}{n}}={\omega }_n^{n-1}$$

---

三个引理

• 消去引理
  当d≠0$d\ne 0$时，有ωdkdn=ωkn${\omega }_{dn}^{dk}={\omega }_n^k$
  证明:ωdkdn=e2dkπidn=e2kπin=ωkn${\omega }_{dn}^{dk}=e^{\frac{2dk\pi i}{dn}}=e^{\frac{2k\pi i}{n}}={\omega }_n^k$

• 折半引理
  当n>0$n>0$且n$n$为偶数，(ωkn)2=ωkn2$({\omega }_n^k{)}^2={\omega }_{\frac{n}{2}}^k$,用文字描述就是n$n$个n$n$次单位根的平方的集合就等于n2$\frac{n}{2}$个n2$\frac{n}{2}$次单位根的集合。
  证明:(ωkn)2=(e2kπin)2=e2kπin×2=e2kπin2=ωkn2$({\omega }_n^k{)}^2=(e^{\frac{2k\pi i}{n}}{)}^2=e^{\frac{2k\pi i}{n}\times 2}=e^{\frac{2k\pi i}{\frac{n}{2}}}={\omega }_{\frac{n}{2}}^k$

• 求和引理
  对于任意的k∈[0,n]$k\in [0,n]$，都有∑n−1j=0(ωkn)j=0$\sum _{j=0}^{n-1}({\omega }_n^k{)}^j=0$
  证明：用等比数列的和的公式，带入推导化简一下就出来了(公式太难打了就读者自己推一推吧QAQ)。

特殊的：ωnn=1${\omega }_n^n=1$

---

那么运用复数和单位根，可以将DFT$DFT$与IDFT$IDFT$降到O(nlog2n)$O(nlo{g}_{2}n)$的复杂度，下面会继续详解方法。

---

马上接近正题了，加油！

蝴蝶变换

其实也叫Cooley−Tukey$Cooley-Tukey$算法，它是将radix−r$radix-r$算法选取2k$2^k$为基，(其实基可以在数据的大小内任意选，但是一般选2$2$来变换)，然后来做变换，也就是按照下标的2k$2^k$进制来进行分治，它一般具有log2kn$lo{g}_{2^k}n$的复杂度，但是只能处理大小为2k$2^k$的整倍数的数据。

例如我们以2$2$为基，来将一个多项式A(x)$A(x)$的系数分成a,b$a,b$两个集合。
令集合大小为n,S=n2$n,S=\frac{n}{2}$,那么就有：a={2Sa1+2S−2a2+⋯+aS−1+aS},b={b1+2b2+⋯+2SbS}$a=\{2^S{a}_1+2^{S-2}{a}_2+\cdots +a_{S-1}+a_S\},b=\{b_1+2b_2+\cdots +2^S{b}_S\}$（其中的系数只是表示下标被分治的标志）。

那么就可以使用蝴蝶变换来神奇的实现该操作，具体形式如下图：

其实我这个图画的不好，（mspaint好难用QAQ）。

可以看这，详细的手动模拟

详细的学术论文

我在这就不多说了，蝴蝶逆变换也就是将ωkn${\omega }_n^k$改为12ω−kn$\frac{1}{2}{\omega }_n^{-k}$就是逆变换了。

逆变换的证明可以看这里超级好的大佬文章，用矩阵的方法证明。

那么代码上也就简单啦！

---

离散傅里叶变换

其实还有连续的傅里叶变换

利用前面的cooley−Tukey$cooley-Tukey$算法，我们一般将基设置为2$2$，那么就是按照多项式的下标的奇偶性分类（前面提出过），所以我们记原多项式为A(x)$A(x)$，它被分成两个(A0(x),A1(x))$\left(A_0(x),A_1(x)\right)$（偶，奇），我们可以将其写成如下形式:

A0(x)=a0+a2x+a4x+⋯=∑i=0n2−1a2⋅i(xi)$$A_0(x)=a_0+a_{2}x+a_{4}x+\cdots =\sum _{i=0}^{\frac{n}{2}-1}{a}_{2\cdot i}(x^i)$$

A1(x)=a1+a3x+a5x+⋯=∑i=0n2−1a2⋅i+1(xi)$$A_1(x)=a_1+a_{3}x+a_{5}x+\cdots =\sum _{i=0}^{\frac{n}{2}-1}{a}_{2\cdot i+1}(x^i)$$

然后根据折半引理

A(x)=A0(x2)+x⋅A1(x2)$$A(x)=A_0(x^2)+x\cdot A_1(x^2)$$

我们将单位根带入，可知所有的xi$x^i$，那么直接用系数与单位根就可以计算了，并且根据折半引理，可以每次按奇偶折半分治下去，复杂度为O(logn)$O(logn)$，每次变换O(n)$O(n)$，所以总的时间复杂度为O(nlogn)$O(nlogn)$。

所以对于k<n2$k<\frac{n}{2}$，我们有：

A(ωkn)=A0((ωkn)2)+ωknA1((ωkn)2)$$A({\omega }_n^k)=A_0(({\omega }_n^k{)}^2)+{\omega }_n^k{A}_1(({\omega }_n^k{)}^2)$$

=A0(ωkn2)+ωknA1(ωkn2)$$=A_0({\omega }_{\frac{n}{2}}^k)+{\omega }_n^k{A}_1({\omega }_{\frac{n}{2}}^k)$$

=∑i=0n2−1a2i(ωkin2)+ωkn∑i=0n2−1a[2i+1](ωkin2)$$=\sum _{i=0}^{\frac{n}{2}-1}{a}_{2i}({\omega }_{\frac{n}{2}}^{ki})+{\omega }_n^k\sum _{i=0}^{\frac{n}{2}-1}{a}_{[2i+1]}({\omega }_{\frac{n}{2}}^{ki})$$

还有一个性质就是

A(ωn2+kn)=A0(ωkn2)+ωn2+knA1(ωkn2)$$A({\omega }_n^{\frac{n}{2}+k})=A_0({\omega }_{\frac{n}{2}}^k)+{\omega }_n^{\frac{n}{2}+k}{A}_1({\omega }_{\frac{n}{2}}^k)$$

又因为ωn2n=−1${\omega }_n^{\frac{n}{2}}=-1$
所以原式就为

A(ωn2+kn)=A0(ωkn2)−ωknA1(ωkn2)$$A({\omega }_n^{\frac{n}{2}+k})=A_0({\omega }_{\frac{n}{2}}^k)-{\omega }_n^k{A}_1({\omega }_{\frac{n}{2}}^k)$$

所以另一半也就可以求出了。

那么这个问题就较好的解决了，在O(nlog2n)$O(nlo{g}_{2}n)$的时间内。

---

离散傅里叶逆变换

IDFT(Inverse Discrete Fourier Transform)$IDFT(InverseDiscreteFourierTransform)$

就是FFT$FFT$的最后一步了(上一步转换为点值表达式后还要O(n)的对于项乘起来，然后在对于乘起来后的点值表达式再进行IDFT)。

IDFT它的实质就是解一个线性方程组，但不会像高斯消元一样，具体的说明可以看前面推荐过的这篇文章，因为数学公式太难打了

---

具体实现

根据蝴蝶变换和折半引理，分治递归处理是最直接的，但是有时效率较差，那么我们深入探究蝴蝶变换的过程发现，可以用迭代的方法，而基为2$2$的变换，实质就是基于二进制位，但是数组顺序会在变换后打乱，所以我们要提前翻转一下，下面看代码，代码中有些解释。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define db double
using namespace std;
const int M=2e6+1e5+10;
const db pi=acos(-1);
struct complex{
    db x,y;
    complex(db a=0,db b=0):x(a),y(b){}
    complex operator +(complex a){return complex(x+a.x,y+a.y);}
    complex operator -(complex a){return complex(x-a.x,y-a.y);}
    complex operator *(complex a){return complex(x*a.x-y*a.y,x*a.y+y*a.x);}
    //定义复数类，也可使用自带的complex，但是速度会比手写的慢。
}a[M],b[M],w[M];
int r[M],len,lg;

void DFT(complex *a,int n,int f){
//  for(int i=1,j=(n>>1),k;i<=n-2;i++){
//      if(i<j)swap(a[i],a[j]);
//      for(k=(n>>1);j>=k;j-=k,k>>=1);
//      if(j<k)j+=k;
//  }每次重新变换
    for(int i=0;i<n;i++) if(i<r[i]) swap(a[i],a[r[i]]);//预处理变换后直接交换
    for(int i=2;i<=n;i<<=1){
        int now=i>>1;
        complex wn=w[i];wn.y*=f;
        //预处理了单位根，如果为逆变换，f=-1，然后将sin项乘以-1
        //不预处理的话精度误差会大一点，每次算的话，wn=complex(cos(2*pi/i),f*sin(2*pi/i))
        for(int j=0;j<n;j+=i){
            complex w=complex(1,0),x,y;
            for(int k=j;k<j+now;k++,w=w*wn){
                x=a[k],y=w*a[k+now];//枚举奇数项和偶数项，然后奇数项乘以单位根的次方
                a[k]=x+y;a[k+now]=x-y;//根据前面推导的式子进行加减
            }
        }
    }
    if(f==-1)for(int i=0;i<n;i++)a[i].x/=n;//其实逆变换每次除以2，可以简单写为最后除以n=2^s
}

void FFT(complex *a,complex *b,int n,int m){
    DFT(a,len,1);DFT(b,len,1);//先将两个多项式转换为点值表达式
    for(int i=0;i<=len;i++) a[i]=a[i]*b[i];//对应项相乘
    DFT(a,len,-1);//逆变换回来
    for(int i=0;i<=n+m;i++) printf("%d ",int(a[i].x+0.5));
    //输出系数，要注意精度误差
}
int x,n,m;
int main(){
//输入两个0~n和0~m的多项式系数，然后求其卷积后输出
//洛谷FFT模板
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++) scanf("%d",&x),a[i].x=x;
    for(int i=0;i<=m;i++) scanf("%d",&x),b[i].x=x;
    for(len=1;len<=n+m;len<<=1,++lg);
    for(int i=0;i<len;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(lg-1));//预处理变换
    for(int i=2;i<=len;i<<=1)w[i]=complex(cos(2*pi/i),sin(2*pi/i));//预处理单位根
    FFT(a,b,n,m);
    return 0;
}

---

结束与例题

类似FFT的还有：

• NTT（快速数论变换）：可以解决FFT的精度问题，用于在取模意义下的卷积。

• FWT（快速沃尔什变换）：解决集合卷积的快速算法，【我的讲解】

• FMT（快速莫比乌斯变换）：和莫比乌斯反演有点关系，我也不清楚，好像也可以解决一些奇怪的集合卷积问题。

---

一些题目：

• 模板题

• 高精度乘法

• [ZJOI2014]力

• 残缺的字符串

• 万径人踪灭

• 九连环(高精快速幂)

• HDU4609 3-idiots

• 我自己的题抛色子（完全背包计数FFT优化）

---

如果有错的地方请指出，Thanks♪(･ω･)ﾉ。