感谢这篇博客,我在这里只是用了CV大法防止他失效了
前言
先解释几个比较容易混淆的缩写吧
DFT:离散傅里叶变换—>$O(n^2)$计算多项式乘法
FFT:快速傅里叶变换—>$O(n \times log(n)$计算多项式乘法
FNTT/NTT:快速傅里叶变换的优化版—>优化常数及误差
FWT:快速沃尔什变换—>利用类似FFT的东西解决一类卷积问题
MTT:毛爷爷的FFT—>非常nb/任意模数
FMT 快速莫比乌斯变化—>感谢stump提供
多项式
系数表示法
设 $A(x)$ 表示一个 $n-1$ 次的多项式
则 $A(x) = \sum_{i=0}^{n-1} a_i \times x^i $
例如 $A(3) = 2 + 3 \times x + x^2 $
如果利用朴素的方法计算两个多项式的乘积的系数表达,复杂度会达到$O(mn)$
第一个多项式中每个系数都需要与第二个多项式的每个系数相乘
点值表示法
将$n$互不相同的$x$带入多项式,会得到$n$个不同的取值$y$
则该多项式被这$n$个点$(x_1,y_1),(x_2,y_2),…,(x_n,y_n)$唯一确定
其中$y_i = \sum_{j=0}^{n-1}a_j∗x_i^j$
例如:上面的例子用点值表示法可以为$(0,2),(1,6),(2,12)$
利用这种方法计算多项式乘法的时间复杂度仍然为$O(n^2)$
(选点$O(n)$,每次计算$O(n)$)
我们可以看到,两种方法的时间复杂度都为$O(n^2)$,我们考虑对其进行优化
对于第一种方法,由于每个点的系数都是固定的,想要优化比较困难
对于第二种方法,貌似也没有什么好的优化方法,不过当你看完下面的知识,或许就不这么想了
一些小知识
向量
同时具有大小和方向的量
在几何中通常用带有箭头的线段表示
园的弧度制
等于半径长的圆弧所对的圆心角叫做1弧度的角,用符号rad表示,读作弧度。用弧度作单位来度量角的制度叫做弧度制
公式:
平行四边形定则
平行四边形定则:$AB+AD=AC$
复数
定义
设$a,b$为实数,$i^2=−1$,形如$a+bi$的数叫复数,其中$i$被称为虚数单位,复数域是目前已知最大的域
在复平面中,$x$代表实数,$y$轴(除原点外的点)代表虚数,从原点$(0,0)$到$(a,b)$的向量表示复数$a+bi$
模长:从原点$(0,0)$到点$(a,b)$的距离,即$\sqrt{a^2+b^2}$
幅角:假设以逆时针为正方向,从x轴正半轴到已知向量的转角的有向角叫做幅角
运算法则
加法:
因为在复平面中,复数可以被表示为向量,因此复数的加法与向量的加法相同,都满足平行四边形定则(就是上面那个)
乘法:
几何定义:复数相乘,模长相乘,幅角相加
代数定义:
单位根
下文中,默认$n$为$2$的正整数次幂
在复平面上,以原点为圆心,$1$为半径作圆,所得的圆叫单位圆。以圆点为起点,圆的$n$等分点为终点,做$n$个向量,设幅角为正且最小的向量对应的复数为$ω_n$,称为$n$次单位根。
根据复数乘法的运算法则,其余$n−1$个复数为$ω_{n}^{2},ω_{n}^{3},…,ω_{n}^{n}$
注意$ω_{n}^{0}=ω_{n}^{n}=1$(对应复平面上以x轴为正方向的向量)
那么如何计算它们的值呢?这个问题可以由欧拉公式解决:
图中向量$AB$表示的复数为8次单位根
单位根的幅角为周角的$\frac{1}{n}$
正片开始
快速傅里叶变换
我们前面提到过,一个$n$次多项式可以被$n$个点唯一确定。
那么我们可以把单位根的$0$到$n−1$次幂带入,这样也可以把这个多项式确定出来。但是这样仍然是$O(n^2)$的
我们假设多项式$A(x)$的系数为$(a_o,a_1,a_2,\ldots,a_{n-1})$
那么有 :
用上高中数学里面的奇偶分析,把该多项式按照奇偶分开,有:
分成奇偶两个多项式 , 有 :
那么结合之前的小知识,我们有了一个大胆的想法:把单位复数带进去
我们将$\omega_n^k (k<\frac{n}{2})$代入,有
然后结合性质把$$也代入 ,有
这两个式子只有一个常数项不同
那么当我们在枚举第一个式子的时候,我们可以$O(1)$的得到第二个式子的值
又因为第一个式子的$k$在取遍$\left[ 0 , \frac{n}{2}−1 \right] $ 时 ,$k+\frac{n}{2}$取遍了$\left[\frac{n}{2},n−1 \right]$
所以我们将原来的问题缩小了一半
而缩小后的问题仍然满足原问题的性质,所以我们可以递归的去解决这个问题
直到多项式仅剩一个常数项,这时候我们直接返回
时间复杂度:
不难看出FFT是类似于线段树一样的分治算法。
因此它的时间复杂度为$O(nlog(n))$
快速傅里叶逆变换
我们上面的讨论是基于点值表示法的。
但是在平常的学习和研究中很少用点值表示法来表示一个多项式。
所以我们要考虑如何把点值表示法转换为系数表示法,这个过程叫做傅里叶逆变换
现有$(y_0,y_1,y_2,\dots,y_{n-1})$为$(a_0,a_1,a_2,\dots,a_{n-1})$的傅里叶变换(点值表示)
设有另一向量$(c_0,c_1,c_2,\dots,c_{n-1})$满足:
设$S(x)=\sum_{i=0}^{n-1}x^i$
将$\omega_n^k$代入得
接下来,在$k!=0$时,等式两边同时乘以$w_n^k$有
将上面两式相减,有
观察得,分子为0,分母不为0
因此,当$k!=0$时$S(\omega_{n}^{k})=0$
另一种情况 : $k==0$ 时 , 显然有$S(\omega_{n}^{k})=n$
因此在这个式子里面:
当$j \neq k$时 , 值为$0$;
当$j = k$时 , 值为$n$;
因此 , 有