Math_FFT

感谢这篇博客，我在这里只是用了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表示，读作弧度。用弧度作单位来度量角的制度叫做弧度制

公式:

$$\begin{align} 1^{\circ} &= \frac{\pi}{180} rad \\ 180^{\circ} &= \pi rad \end{align}$$

平行四边形定则

平行四边形定则：$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轴正半轴到已知向量的转角的有向角叫做幅角

运算法则

加法：

因为在复平面中，复数可以被表示为向量，因此复数的加法与向量的加法相同，都满足平行四边形定则（就是上面那个）

乘法：

几何定义：复数相乘，模长相乘，幅角相加

代数定义：

$$\begin{align} & \qquad (a+bi)∗(c+di)\\ &=ac+adi+bci+bdi^2\\ &=ac+adi+bci−bd\\ &=(ac−bd)+(bc+ad)i\\ \end{align}$$

单位根

下文中，默认$n$为$2$的正整数次幂

在复平面上，以原点为圆心，$1$为半径作圆，所得的圆叫单位圆。以圆点为起点，圆的$n$等分点为终点，做$n$个向量，设幅角为正且最小的向量对应的复数为$ω_n$，称为$n$次单位根。

根据复数乘法的运算法则，其余$n−1$个复数为$ω_{n}^{2},ω_{n}^{3},…,ω_{n}^{n}$
注意$ω_{n}^{0}=ω_{n}^{n}=1$（对应复平面上以x轴为正方向的向量）

那么如何计算它们的值呢？这个问题可以由欧拉公式解决:

$$\omega_{n}^{k}=\cos\ k \times \frac{2\pi}{n}+i\sin k \times \frac{2\pi}{n}$$

图中向量$AB$表示的复数为8次单位根
单位根的幅角为周角的$\frac{1}{n}$

$$\begin{align} \omega_{n}^{k}&=\cos k\dfrac{2\pi}{n}+i\sin k\dfrac {2\pi }{n} \\ \omega_{2n}^{2k}&=\omega_{n}^{k}\\ \omega_{n}^{k+\frac{n}{2}}&=-\omega_{n}^{k}\\ \omega_{n}^{0}&=\omega_{n}^{n}=1\\ \end{align}$$

正片开始

快速傅里叶变换

我们前面提到过，一个$n$次多项式可以被$n$个点唯一确定。

那么我们可以把单位根的$0$到$n−1$次幂带入，这样也可以把这个多项式确定出来。但是这样仍然是$O(n^2)$的

我们假设多项式$A(x)$的系数为$(a_o,a_1,a_2,\ldots,a_{n-1})$

那么有 ：

$$A(x)=a_0+a_1 \times x+a_2 \times {x^2}+a_3 \times {x^3}+a_4 \times {x^4}+a_5 \times {x^5}+ \dots+a_{n-2} \times x^{n-2}+a_{n-1} \times x^{n-1}$$

用上高中数学里面的奇偶分析，把该多项式按照奇偶分开，有：

$$A(x)=(a_0+a_2 \times {x^2}+a_4 \times {x^4}+\dots+a_{n-2} \times x^{n-2})+(a_1 \times x+a_3 \times {x^3}+a_5 \times {x^5}+ \dots+a_{n-1} \times x^{n-1})$$

分成奇偶两个多项式 ， 有 ：

$$\begin{align} A_1(x) &=a_0+a_2 \times {x}+a_4 \times {x^2}+\dots+a_{n-2} \times x^{\frac{n}{2}-1} \\ A_2(x) &=a_1+a_3 \times {x}+a_5 \times {x^2}+ \dots+a_{n-1} \times x^{\frac{n}{2}-1}\\ A(x) &=A_1(x^2)+xA_2(x^2) \end{align}$$

那么结合之前的小知识，我们有了一个大胆的想法：把单位复数带进去

我们将$\omega_n^k (k<\frac{n}{2})$代入，有

$$\begin{align} A(\omega_n^k) &=A_1(\omega_n^{2k})+\omega_n^kA_2(\omega_n^{2k})\\ &=A_1(\omega_{\frac{n}{2}}^{k})+\omega_n^kA_2(\omega_{\frac{n}{2}}^{k}) \end{align}$$

然后结合性质把$$也代入 ，有

$$\begin{align} A(\omega_n^{k+\frac{n}{2}}) &=A_1(\omega_n^{2k+n})+\omega_n^{k+\frac{n}{2}}(\omega_n^{2k+n})\\ &=A_1(\omega_n^{2k}*\omega_n^n)-\omega_n^kA_2(\omega_n^{2k}*\omega_n^n)\\ &=A_1(\omega_n^{2k})-\omega_n^kA_2(\omega_n^{2k}) \end{align}$$

这两个式子只有一个常数项不同
那么当我们在枚举第一个式子的时候，我们可以$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})$满足：

$$\begin{align} c_k &=\sum_{i=0}^{n-1}y_i(\omega_n^{-k})^i\\ &=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j(\omega_n^i)^j)(\omega_n^{-k})^i\\ &=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j(\omega_n^j)^i)(\omega_n^{-k})^i\\ &=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j(\omega_n^j)^i(\omega_n^{-k})^i)\\ &=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_j(\omega_n^j)^i(\omega_n^{-k})^i\\ &=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_j(\omega_n^{j-k})^i\\ &=\sum_{j=0}^{n-1}a_j(\sum_{i=0}^{n-1}(\omega_n^{j-k})^i) \end{align}$$

设$S(x)=\sum_{i=0}^{n-1}x^i$
将$\omega_n^k$代入得

$$S(\omega_n^k)=1+(\omega_n^k)+(\omega_n^k)^2+\dots(\omega_n^k)^{n-1}$$

接下来，在$k!=0$时，等式两边同时乘以$w_n^k$有

$$\omega_n^kS(\omega_n^k)=\omega_n^k+(\omega_n^k)^2+(\omega_n^k)^3+\dots(\omega_n^k)^{n}$$

将上面两式相减，有

$$\begin{align} \omega_n^kS(\omega_n^k)-S(\omega_n^k) &= (\omega_n^k)^{n}-1\\ S(\omega_n^k) &= \frac{(\omega_n^k)^{n}-1}{\omega_n^k-1}\\ S(\omega_n^k) &= \frac{(\omega_n^n)^{k}-1}{\omega_n^k-1}\\ S(\omega_n^k) &= \frac{1-1}{\omega_n^k-1} \end{align}$$

观察得，分子为0，分母不为0

因此，当$k!=0$时$S(\omega_{n}^{k})=0$

另一种情况 ： $k==0$ 时 ， 显然有$S(\omega_{n}^{k})=n$

因此在这个式子里面：

$$c_k=\sum_{j=0}^{n-1}a_j(\sum_{i=0}^{n-1}(\omega_n^{j-k})^i)$$

当$j \neq k$时 ， 值为$0$；
当$j = k$时 ， 值为$n$；

因此 ， 有

$$c_k=na_k$$ $$a_k=\frac{c_k}{n}$$