FFT [TPLY]

题目链接

资料推荐

orz大佬博客

知识点

书籍推荐

ACM/ICPC 算法基础训练教程 7.4快速傅里叶变换
算法导论 30章多项式与快速傅里叶变换

觉得看不懂很正常,知识点很抽象需要逐步理解
而对于本文,本文作用为对两位大佬内容解读并且加入自己看法
读者可以先花时间阅读以上推荐的文字,产生一定理解再读本文.由于作者很弱,可能会产生错误,还请大神帮忙指出.

正文

Part1.初识FFT

作用:求多项式乘法的系数(就是初中学的多项式)
FFT多项式乘法与普通形式有差异

一般多项式乘多项式法则:
多项式与多项式相乘,先用一个多项式的每一项与另一个多项式的每一项相乘,再把所得的积相加。举一个例子由多项式乘多项式法则可以得到(a+b)(c+d)=a(c+d)+b(c+d)=ac+ad+bc+bd

FFT'绕圈'法
FFT处理多项式相乘,先从多项式最普通的表达形式---系数表达形式转化成点值表达形式再进行点值乘法.最后,再将点值乘法的结果转回系数表达形式.
而从-系数表达形式转化成点值表达形式的过程,我们叫做DFT,即离散傅里叶变换.
点值乘法的结果转回系数表达形式的步骤,我们称之为离散傅里叶变换的逆运算,也叫插值.

看了这么多文字,相信你有一点晕晕乎乎的,下面是概念解释
1~对于点值表达式我的理解 : 点值表达形式就是用若干函数上的点的坐标来表示该函数,比如 $f(x)=x^2-x+2=\{ ( 0 , 2 ) , ( 1 , 2 ) , ( 2 , 4 ) \}$
2~点值表达式的计算:
假设我们现在有用点乘表示的多项式
A(x)={(0,1),(1,2),(2,7)}
B(x)={(0,2),(1,2),(2,4)}
[P.S.:点乘表达式能运算的条件是两个点要有相同的x值]
C(x)={(0,2×1),(1,2×2),(2,7×4)}={(0,2),(1,4),(2,28)}

FFT流程图如下:(借鉴他人博客)

part2.复数

0.为什么要学习复数?
YL大佬原话:"学习复数,所有这些七七八八的定理,都是为了FFT的奇妙变换!"

所以,为了FFT,好好学习复数吧!(再一次ORZ YL大佬)

1.复数的定义:我们把形如a+bi(a,b均为实数)的数称为复数,其中a称为实部,b称为虚部,i称为虚数单位,i的值为$\sqrt{-1}$
2.单位根的定义:数学上,n次单位根是n次幂为1的复数。
单位根的概念不理解很正常,下面举个例子(来自百度百科)
单位的一次根有一个:1
单位的二次根有两个:+1和-1。
单位的三次根是:
$\{ 1 , \frac{-1+\sqrt{3}i}{2} , \frac{-1-\sqrt{3}i}{2} \}$
咱们证明一下
$(\frac{-1+\sqrt{3}i}{2})^3=(\frac{-1+\sqrt{3}i}{2})^2×(\frac{-1+\sqrt{3}i}{2})$
....................$=(\frac{1+3i^2-2\sqrt{3}i}{4})×(\frac{-1+\sqrt{3}i}{2})$
....................$=(\frac{-2-2\sqrt{3}i}{4})×(\frac{-1+\sqrt{3}i}{2})$
....................$=(\frac{(-2)×(1+\sqrt{3}i)×(\sqrt{3}i-1)}{8})$
....................$=-(\frac{1}{4})×(3i^2-1)$
....................$=-(\frac{1}{4})×(-4)$
....................$=1$
所以$\frac{-1+\sqrt{3}i}{2}$是单位的三次根
单位的四次根是${1,+i,-1,-i}$

希望你已经理解了什么是单位复数根(单位根),咱们继续

对于$w_n=e^{2πi/n}$我们称$w _ n$为$n$次单位根(前面讲了n次单位跟哦)
(普及一下:复数指数形式的定义:$e^{iu}=cos(u)+isin(u)$)
下面有一些定理需要记住(YL大佬的忠告)
PS由于太弱不会证明,网上有很多证明哦
(w上标表示指数)
消去引理
$$\omega^{dk} _ {dn}=\omega^{k} _ {n}$$
这个引理非常非常重要哦,你后面一定一定会见到!
非常,非常重要!记住!
折半引理
$$
(\omega^{k+\frac{n}{2}} _ {n})^{2}=\omega^{2k+n} _ {n}=\omega^{2k} _ {n}\omega^{n} _ {n}=(\omega^{k} _ {n})^{2}
$$
求和引理
$$
\Sigma^{n-1} _ {j=0}(\omega^{k} _ {n})^{j}=0
$$

这些复杂的数学公式可能会使你觉得枯燥无味,但为后面的运算奠定了重要的基础,了解一下下啦!

Part3.DFT与-DFT进阶

在本章内于括号里面的数为什么是$\omega^{k} _ {n}$而不是x,你要到FFT才能明白.但本章内容中的$\omega^{k} _ {n}$你可以当成x看(下一章就不行了)

DFT
对于k=0~n-1,定义:
$$y _ k=A(\omega^{k} _ {n}) = \Sigma^{n-1} _ {j=0} a _ j(\omega^{k} _ {j})^j$$
对于这个式子,你这么看$y _ k=A(x)=\Sigma^{n-1} _ {j=0} a _ j(x)^j$
我们知道DFT求的是点乘
点乘就是坐标(前面忘讲了:坐标的数量一定要大于等于n,证明网上有详细解释)
平时你是怎么求坐标的?
选定一个x值,把x值带到里面求出y
上面这个式子就是这么做的啦(还不懂就再看看多项式的系数表达式)

所以我们继续分析,对于每一个x,我们都要O(n)地将值带到多项式里求值,我们最少要n个坐标,所以总复杂度是$O(n×n)$

最后我们将得到的y称为a的离散傅里叶变换,记作$y=DFT_n(a)$ (这里的$y$,$a$指的是所有的$y _ k,a _ k$($k$有$n$种,也就是要取k个))

这个定义先记着,还要注意的是,这一步的作用是将系数表达形式变成点乘表达形式$O(n×n)$.再用之前的点乘算法算出点乘的结果$O(n)$(Part1.讲了点乘,复杂度证明很显然).最后用下面的离散傅里叶逆变换(我叫它-DFT),再换回去$O(n×n)$所以总复杂度为$O(n×n)$

-DFT
非常抱歉我还是不会证,只能摆出结果$$对于y_k = \Sigma^{n-1} _ {i=0}a _ i(x)^i$$
$$有a _ k = \frac{1}{n}\Sigma^{n-1} _ {i=0}y _ i(x)^i$$
再对比DFT公式
$$y_k = \Sigma^{n-1} _ {j=0} a _ j(x)^j$$
可以发现,DFT-DFT的差别很小,基本上只是y,a调换了一下罢了(也有不同的...)

Part4 FFT水落石出

终于来到了最后,前面所有令人头大的背景知识,都是为了这一章而服务.
所以这一章是至关重要的.
如果前面还没有完全理解,请重新巩固扎实.

网上都说,FFT的复杂度为$O(nlgn)$
那是怎么来的呢?
答案是:神奇的分治
先把A(x)这个多项式拆分成奇数项与偶数项
$$A^{[0]}(x) = a _ 0 + a _ 2x + a _ 4x^2 + ... + a _ {n-2}x^{\frac{n}{2} - 1}$$
$$A^{[1]}(x) = a _ 1 + a _ 3x + a _ 5x^2 + ... + a _ {n-1}x^{\frac{n}{2} - 1}$$
$$A(x) = A^{[0]}(x^2) + xA^{[1]}(x^2) $$
这个是正确的,希望读者拿起草稿纸自己演算一遍
咱们把这个多项式拆分成这样子以后
复数闪亮登场
开始用复数的公式了哦
咱们不妨把$\omega^{k}$带入到x中去
$$A(\omega^k_n)=A^{[0]}((\omega^k_n)^2) + \omega^k_n A^{[1]}((\omega^k_n)^2)$$
然后,通过之前提到过的单位复数根消去引理我们可以得到(说了消去引理非常重要)
咱们用消去引理把$(\omega^k _ n)^2$化一下
$(\omega^k _ n)^2$=$\omega^{2k} _ n$

.............$=\omega^{\frac{2k}{2}} _ {\frac{n}{2}}$

.............$=\omega^{k} _ {\frac{n}{2}}$
所以
原式=$$A^{[0]}(\omega^k _ {\frac{n}{2}}) + \omega^k _ n A^{[1]}(\omega^k _ {\frac{n}{2}}) $$
又因为$$\omega^{\frac{n}{2}} _ {n}=\omega _ {2}=e^{k\pi i}= cos k\pi + i sin k\pi = -1$$
所以
$$A(\omega^{k+\frac{n}{2}} _ n)=A^{[0]}(\omega^k _ {\frac{n}{2}}) - \omega^k _ n A^{[1]}(\omega^k _ {\frac{n}{2}})$$
这样就从n个变成了${\frac{n}{2}}$个,缩了一半
最后,再观察每次按照奇偶位置分割所形成的树(博主谢谢又借一下你的图片)

我们可以发现每个数和他二进制相反的位置互换!!(比如,1与4发生交换)
所以就可以用迭代的方式了

代码

FFT原理是一回事,代码又是另一回事,最好还是把它背下来

总会有用的!

P1919 【模板】A×B Problem升级版(FFT快速傅里叶)

几点注意
pi 最好不要手写(当然如果你能背到小数点后十几位我也不栏你)
不然很可能出精度问题
最好手写Complex速度快很多
注意一些从0开始的地方
加油哦!

END