FFT
卷积与$\texttt{DFT,IDFT}$的思想
$\texttt{FFT}$，即快速傅里叶变换（英文名$\texttt{Fast Fourier Transform}$），是一个用来求卷积的方法。
卷积这个词以后会经常用到，所以先普及一下这个词到底是什么意思。
形如$h_n=\sum\limits_{i}f_ig_{n-i}$的式子，将$h$称为$f$和$g$的卷积。
但是这个东西有一个更直观的名字：多项式乘法！
为什么呢？这里解释一下。
比如说有两个$n$次的多项式$F(x)$和$G(x)$，它们乘起来为$H(x)$，这些多项式的系数数列依次为$f,g,h$，有
为什么呢？
众所周知，$H(x)=\sum\limits_{i=0}^{n}h_ix^i$。
为了凑一个$x^i$，如果$F(x)$出$f_jx^j$的话，那么$G(x)$只能出$g_{i-j}x^{i-j}$。
所以，$h_ix^i=\sum\limits_{j=0}^{i}f_jx^j\cdot g_{i-j}x^{i-j}$
把$x^i$约去，有
然而，普通的多项式乘法要对$F(x)$和$G(x)$每一项进行相乘，时间复杂度为$O(n^2)$，布星。
所以说，有没有更快一点的方法呢？
还真有！！
首先看一个问题。
给定有$n$个点$(a_i,F(a_i))$。$F(x)$是几次多项式呢？怎么求$F(x)$呢？
先考虑一个简单的，比如说给出了两个点,$(0,1)$和$(1,3)$，怎么求$F(x)$？
比如说，假设$F(x)$是一次的。那么设$F(x)=a_0x+a_1$，于是将$(0,1),(1,3)$代入$F(x)$，那么有：
解得
而当$F(x)$为二次多项式时，即$F(x)=a_0x^2+a_1x+a_2$，那么可列出如下式子：
这样子我们最多得到
$F(x)$为二次多项式就已经不能精确解出系数的值了，那么更高次多项式更不行了。
所以说给两个点的值能确定一个一次多项式。
可以尝试一下$3$个点，它是可以确定一个二次多项式的（可能不能确定一个一次多项式，因为方程组可能无解）。
根据以上的实验和常识可知，$n$个点最多确定一个$n-1$次多项式。
那么我们现在理论上证明一下。
首先看一个小问题。
给定$m$个值$a_i$和$n$次多项式$F(x)$，求$F(a_i)$。
考虑把它写成矩阵的形式，有
所以
根据基本线代常识，只有方阵才是可逆矩阵，所以只有右边的矩阵为方阵，即为范德蒙德矩阵时它才可能有逆，也即可以解出系数数列$f$。
然而，范德蒙德矩阵吗一定可逆吗？
由范德蒙德矩阵的行列式公式可知，矩阵可逆当且仅当$a_1,a_2\cdots a_m$两两不等。
这里就证明了最多这个条件。
所以$n+1=m$，即$n=m-1$，即确定的多项式为$m-1$次。
所以说，一个$n-1$次多项式与它的曲线上的$n$个点的集合是等价的，而这个集合，叫做多项式的点值表达。
下面说点值表达是怎么优化多项式乘法的。
两个多项式相乘，如果是用系数乘法，是$O(n^2)$的，但点值乘法只需对应的点值相乘，时间复杂度为$O(n)$。
但是你插值的时候会出问题。
两个$n$次多项式相乘，乘出来的多项式明摆的是$2n$次的，可是两个$n$次多项式给出的点值只有$n+1$个。在称完之后插不出确定的多项式。怎么办？
考虑扔一些点上去凑即可。这些点只是起到附加作用，并没有对原来的多项式有影响。
所以点值表达有什么用？还不是加速多项式乘法。
于是自然的考虑先求点值，相乘后插值即可。这就是$\texttt{FFT}$的流程。
把系数表达转换为点值表达叫做$\texttt{DFT}$，
把点值表达转换为系数表达叫做$\texttt{IDFT}$。
什么鬼！！求值是$O(n^2)$的，插值是$O(n^3)$的，你跟我讲这个？？
别着急。你只要代的数好的话就可以大大简化。
复数的性质以及单位根的引入
先来回答上面的问题。
想我们这种小蒟蒻只会代入人畜无害的有理数，但这对计算无益。
但这时，有一位搞复数的$\texttt{dalao}$横空出世，他就是傅里叶。
这人啊，把单位根代入多项式想求点值表达，可是由于单位根有一些优秀的性质，就可以分治做到$O(n\log n)$。
接着，我们来介绍复数。
数轴可以表示任意实数，对吧。
可是尽管有数轴还不足以解决问题。比如说解方程$x^2=-1$。
数轴上没有数的平方等于$-1$。于是数学家们提出了一个东西叫做$\mathrm{i}$，规定了$\mathrm{i}^2=-1$。
所以说，刚刚的方程就有了两个解$x_1=\mathrm{i},x_2=-\mathrm{i}$。
而这个$\mathrm{i}$就叫做虚数单位。数学家们把形如$z=a+b\mathrm{i}$的数叫做复数，其中$a$叫做实部，$b$叫做虚部。
可是仅仅有一根数轴无法表示复数，于是就出现了一根轴，两根轴共同组成了一个平面，叫做复平面。就像这样
横着的那根轴叫做实轴，用来记录复数的实部。与实轴垂直的轴叫做虚轴，记录复数的虚部。
于是我们就可以用一个复平面来表示复数了。如下图
红点表示的复数为$-1+2\mathrm{i}$，蓝点表示的复数则为$2+4\mathrm{i}$。
加减法的话不多说。乘法当一次多项式成就可以了。除法的话有套路。
首先求$\frac{1}{a+b\mathrm{i}}$。
考虑分母有理化，分子分母同乘共轭复数，有
所以有
接着是模长和辐角的概念。
模长是什么？说白了，就是复数所对应的复平面上的点到原点的距离。也即复数$a+b\mathrm{i}$的模长为$\sqrt{a^2+b^2}$。
辐角的话呢，就是如下图
所谓辐角，就是红点与原点的连线和实轴上那根黑线所成的夹角。
如果红点对应的复数为$z$，那么$z$的辐角记作$\arg z$。
接下来就是终点了。
负数的乘法：模长相乘，辐角相加。
我们用一个图形说明这一点。
设$A,B$代表的复数依次为$a+b\mathrm{i},c+d\mathrm{i}$，则
乘起来，有
还有
所以，只需要证明$(ac-bd)^2+(bc+ad)^2=(a^2+b^2)(c^2+d^2)$
左边展开，有
命题得证。
要想证明第二个命题，我们得用一个公式。
暴力拆开，得
右边展开，有
命题得证。
这里下发一个$\texttt{demo}$，以上的图片就是基于它而绘制的。
于是讲讲单位根这种东西。
首先证明欧拉公式：$e^{\mathrm{i}\theta}=\cos\theta+\mathrm{i}\sin\theta$
左边泰勒展开，有
右边那东西，直观地看，就是这样的
分组，有
然后可以发现括号内的东西为$\cos\theta$和$\sin\theta$的麦克劳林级数，于是命题得证。
接着可以看到，复数$\cos\theta+\mathrm{i}\sin\theta$所对应的复平面的点为$(\cos\theta,\sin\theta)$，这个点有一个特殊的性质，那就是
无论$\theta$为多少，这个点总在一个半径为$1$的单位圆上！
不仅如此，我们还有一个小小的推论，就是$(\cos\theta+\mathrm{i}\sin\theta)^n=\cos(n\theta)+\mathrm{i}\sin(n\theta)$
然后要解一个有$n$个解的方程：$z^n=1$，其中$z$为复数。
我们知道，$z=1$为一合法解，但剩下的解呢？？
考虑换元做。设$z=a+b\mathrm{i}$，那么它的模长为$\sqrt{a^2+b^2}$，于是$z^n$的模长就为$(\sqrt{a^2+b^2})^n$，而它又要等于$1$，所以，$z$的模长就是$1$了，也即$z$在一个单位圆上。
所以可设$z=\cos\theta+\mathrm{i}\sin\theta$，所以
所以
在$\cos x$和$\sin x$的一个周期内，满足上述方程组的$n\theta$只能为$0$。
所以上述方程组等价于$n\theta=2k\pi$，所以解为
其中，$0\leq k\leq n-1$。
这些$z$就被叫做$n$次单位根，第$i$个记作$\omega_n^i$，有
这里下发一个帮助理解的$\texttt{demo}$
接着是单位根的性质（满屏三角函数来袭）
- 对于任意的$n$，都有$\omega_n^0=1$
显然的，有
- 消去引理：$\omega_{dn}^{dk}=\omega_n^k$
左边暴力搞一搞，有
- 折半引理：$\omega_n^{k+\frac{n}{2}}=-\omega_n^k$，其中$n$为偶数。
左边暴力搞一搞，有
于是有
和
这样一来，就有
命题得证。
- 求和引理：$\sum\limits_{i=0}^{n-1}\omega_n^i=0$
先证一个小小的引理：$\omega_n^k=(\omega_n^1)^k$
证明如下
所以，有