参考自 $\text{OI-wiki}$，
口胡的结论证明为自行补充。
$\text{Complex Number}$ 复数
$\text{Difinition}$ 定义
引入 虚数单位 $\rm i$ ，其值满足 $\rm i^2=-1$，定义 复数域 $\mathbb{C}=\mathbb{R}[i]$。
定义 复数的代数形式 为 $z=a+b\rm i\displaystyle(a,b\in\mathbb{R})$。此时若 $b\not=0$，称 $b$ 为虚数，在此条件下若 $a=0$，称 $b$ 为纯虚数。
定义 实部 $\text{Re}(z)=a$，虚部 $\text{Im}(z)=b\rm i$。
$\text{Geometrical Significance}$ 几何意义
复数无法在一维下表示。
复数相等：对于复数 $z_1=a_1+b_1\text{i}$，$z_2=a_2+b_2\text{i}$，若 $a_1=a_2\wedge b_1=b_2$，则 $z_1,z_2$ 相等。
由复数相等的定义，复数 $z=a+b\rm i$ 写作数对 $(a,b)$ ，则复数集合与平面直角坐标系上的点集合构成双射，称这样的平面为 复平面，其中 $x$ 轴为 实轴，$y$ 轴为 虚轴。
由于复平面上的所有点 $Z(a,b)$ 均唯一对应 向量 $\overrightarrow{OZ}=(a,b)$，可以推出复数集合与复平面内的向量集合也构成双射。
因此定义复数 $z$ 的模 $\mid z\mid$ 为其对应的向量 $\overrightarrow{OZ}$ 的模，即 $\mid z\mid=\sqrt{a^2+b^2}$。定义模为 $1$ 的复数为 单位复数，全体单位复数在复平面上构成 单位圆周。
由向量的定义，虚数 不可比较大小。
以上为平面直角坐标系下的分析，同理，可以使用 极坐标系 表示复平面，复数 $z$ 的极坐标为 $(r,\theta)$，其中 $r=\mid z\mid$。
此时定义复数 $z=a+b\text{i}$ 的 辐角 $\theta=\text{Arg } z$ 为实轴正向到复数 $z$ 对应向量的夹角，可得 $\theta$ 满足关系式为 $\theta=\tan \frac{y}{x}$。
可以发现任意非零复数有无数个辐角，$\text{Arg }z$ 实质上为一个集合，因此定义 辐角主值（主辐角） $\text{arg } z$ 为其中一个特定值，满足 $-\pi<\text{arg }z\leq\pi$。
因此 $\text{Arg }z={\text{arg }z+2k\pi\mid k\in\mathbb{Z}}$。
$\text{Operations}$ 运算
给定复数 $z_1=a_1+b_1\text{i}$，$z_2=a_2+b_2\text{i}$，则它们对应的向量分别为 $\overrightarrow{OZ_1}=(a_1,b_1),\overrightarrow{OZ_2}=(a_2,b_2)$，极坐标为 $(\mid z_1\mid,\theta_1),(\mid z_2\mid,\theta_2)$。
加减法
加法：
\[z_1+z_2=(a_1+a_2)+(b_1+b_2)\rm i\]减法：
\[z_1+z_2=(a_1-a_2)+(b_1-b_2)\rm i\]以加法为例，考虑对应的向量运算，有：
\[\overrightarrow{OZ_1}+\overrightarrow{OZ_2}=(a_1+a_2,b_1+b_2)\]可以发现复数加法规则及结果与向量一致，同时也满足 交换律 与 结合律。
乘法
\[z_1\cdot z_2 = (a_1+b_1\rm{i}\displaystyle)(a_2+b_2\rm i\displaystyle)=(a_1a_2-b_1b_2)+(a_1b_2+a_2b_1)\text{i}\]$\text{OI-wiki}$ 上说与向量叉乘形式类似，但二维向量叉乘 $\overrightarrow{OZ_1}\times\overrightarrow{OZ_2}=(a_1b_2-a_2b_1)\rm i$，从坐标、模长等角度均看不出相似性。
这里与坐标变化的相关性最好还是需要放到极坐标下研究，设复数相乘结果的极坐标为 $(r,\theta)$。显然有 $\sqrt{(a_1a_2-b_1b_2)^2+(a_1b_2+a_2b_1)^2}=\sqrt{a_1^2+b_1^2}\cdot\sqrt{a_2^2+b_2^2}$，因此有 $r=\mid z_1\cdot z_2\mid = \mid z_1\mid\cdot\mid z_2\mid$。
由和差角公式，有：
\[\begin{align*} \tan(\theta_1+\theta_2)&=\frac{\tan(\theta_1)+\tan(\theta_2)}{1-\tan(\theta_1)\tan(\theta_2)}\\ &=\frac{\frac{b_2}{a_1}+\frac{b_1}{a_2}}{1-\frac{b_1b_2}{a_1a_2}}\\ &=\frac{a_1b_2+a_2b_1}{a_1a_2-b_1b_2}\\ &=\tan(\theta) \end{align*}\]由此可得结论，两复数相乘，极坐标辐角相加模相乘。
除法
当 $z_2\not= 0$ 时，有：
\[\frac{z_1}{z_2}=\frac{a_1+b_1\rm i\displaystyle}{a_2+b_2\rm i\displaystyle}=\frac{(a_1+b_1\rm i\displaystyle)(a_2-b_2\rm i\displaystyle)}{(a_2+b_2\rm i\displaystyle)(a_2-b_2\rm i\displaystyle)}=\frac{a_1a_2+b_1b_2}{a_2^2+b_2^2}+\frac{-a_1b_2+a_2b_1}{a_2^2+b_2^2}\rm i\]与乘法同理，两复数相除，极坐标辐角相减模相除。
共轭
对于复数 $z=a+b\rm i$，定义其共轭复数 $\overline{z}=a-b\rm i$。
一组共轭复数在复平面上的位置关于实轴对称。
$\text{Formulas and Functions}$ 相关公式及函数
欧拉公式
对于任意 实数 $x$ 有：
\[e^{\text{i} x}=\cos x+\rm i\displaystyle\sin x\]复指数函数
仿照实数指数函数，定义 $f(z)=e^z=e^{x+\rm i\displaystyle y}=e^x\cdot e^{\rm i\displaystyle y}$。
由欧拉公式 $e^{\rm i\displaystyle x}=\cos x+\rm i\displaystyle\sin x$，带入得到 复指数函数 定义为：
\[\text{exp } z=e^x(\cos y+\rm i\displaystyle\sin y)\]以上是我的理解，$\text{OI-wiki}$ 上的定义如下：
对于复数 $z=x+\rm i\displaystyle y$，函数 $f(x)=e^x(\cos y+\rm i\displaystyle\sin y)$ 满足 $f(x_1+x_2)=f(x_1)f(x_2)$。由此给出 复指数函数 的定义：
\[\text{exp } z=e^x(\cos y+\rm i\displaystyle\sin y)\]
$\text{OI-wiki}$ 上所述的几条性质以及我的证明：
- 模恒正：$\mid\text{exp }z\mid=\text{exp }x>0$。
proof.
\[\begin{align*} \mid\text{exp } z\mid&=\sqrt{(e^x\cos y)^2+(e^x\sin y)^2}\\ &=\sqrt{e^{2x}(\cos^2 y+\sin^2 y)}\\ &=\sqrt{e^{2x}}=e^x>0 \end{align*}\]同时有 $\text{exp }x=e^x$，因此 $\mid\text{exp }z\mid=\text{exp }x$。
- 辐角主值 $\text{arg exp }z=y$。
proof.
\[\begin{align*} \tan(\text{arg exp }z)=\frac{e^x\sin y}{e^x\cos y}=\tan y \end{align*}\]辐角主值满足 $-2\pi<\text{arg exp }z\leq 2\pi$，事实上 $y$ 不一定满足这一点。
所以需要更正为 $y\in\text{Arg exp }z$。
- 加法定理 $\text{exp}(z_1+z_2)=\text{exp}(z_1)\text{exp}(z_2)$。
proof.
由于有欧拉公式，$\text{exp }z=e^x(\cos y+\rm i\displaystyle\sin y)=e^x\cdot e^{\text{i}y}$。
因此有：
\[\begin{align*} \text{exp}(z_1)\text{exp}(z_2)&=(e^{x_1}\cdot e^{\rm i\displaystyle y_1})(e^{x_2}\cdot e^{\rm i\displaystyle y_2})\\ &=(e^{x_1+x_2}\cdot e^{\rm i\displaystyle (y_1+y_2)})\\ &=e^{x_1+x_2}(\cos(y_1+y_2)+\rm i\displaystyle\sin(y_1+y_2))\\ &=\text{exp}(z_1+z_2) \end{align*}\]- 周期性：$\text{exp }z$ 是以 $2\pi\rm i$ 为基本周期的周期函数。
proof.
\[\text{exp}(z+2\pi\rm i\displaystyle)=e^{x}(\cos(y+2\pi)+\rm i\displaystyle\sin(y+2\pi))\]由于 $\cos,\sin$ 均以 $2\pi$ 为基本周期，因此
\[e^{x}(\cos(y+2\pi)+\rm i\displaystyle\sin(y+2\pi))=e^x(\cos y+\rm i\displaystyle\sin y)=\text{exp }z\]复三角函数
对于复数 $z=x+\text{i}y$ 定义 复三角函数 如下：
\[\begin{align*} \cos z = \frac{\text{exp}(\rm i\displaystyle z)+\text{exp}(-\rm i\displaystyle z)}{2}\\ \sin z = \frac{\text{exp}(\rm i\displaystyle z)-\text{exp}(-\rm i\displaystyle z)}{2\rm i} \end{align*}\]若取 $z\in \rm R$，则由 欧拉公式 有：
\[\begin{align*} \cos z = \text{Re}(e^{\text{i}z})\\ \sin z = \text{Im}(e^{\text{i}z}) \end{align*}\]$\text{OI-wiki}$ 上所述的几条性质以及我有的不会证明：
- 奇偶性：正弦函数是奇函数，余弦函数是偶函数。
proof.
正弦函数：
\[\sin(-z)=\frac{\text{exp}(-\text{i}z)-\text{exp}(\text{i}z)}{2\text{i}}=-\sin(-z)\]余弦函数：
\[\cos(-z)=\frac{\text{exp}(-\text{i}z)+\text{exp}(\text{i}z)}{2}=\cos(z)\]- 三角恒等式：通常的三角恒等式都成立，例如平方和为 $1$，或者角的和差公式等。
proof. $\cos^2 z+\sin^2 z=1$
\[\begin{align*} \cos^2 z+\sin^2 z &= (\frac{\text{exp}(\rm i\displaystyle z)+\text{exp}(-\rm i\displaystyle z)}{2})^2+(\frac{\text{exp}(\rm i\displaystyle z)-\text{exp}(-\rm i\displaystyle z)}{2\text{i}})^2\\ &= \text{exp}(\text{i}z)\text{exp}(-\text{i}z)\\ &= \text{exp}(\text{i}z-\text{i}z)\\ &=\text{exp}(0) = 1 \end{align*}\]角的和差公式？太麻烦了不证。
- 周期性正弦与余弦函数以 $2\pi$ 为基本周期。
proof.
正弦函数：
\[\sin(z+2\pi)=\frac{\text{exp}(\text{i}z+2\pi\text{i})-\text{exp}(-\text{i}z-2\pi\text{i})}{2\text{i}}\]由于 $\text{exp}$ 函数以 $2\pi\text{i}$ 为基本周期，因而得证。
余弦函数同理。
- 零点：实正弦与实余弦函数的全体零点，构成了复正弦与复余弦函数的全体零点。这个推广没有引进新的零点。
proof.
还没学过函数零点，暂时不会。
- 模的无界性：复正弦与复余弦函数，模长可以大于任意给定的正数，不再像实正弦与实余弦函数一样被限制在 $1$ 的范围内。
proof.
感性理解是容易的，严谨证明没有必要 （其实是因为反证法设一个上界再解定义域推矛盾没解出来）。
$\text{Expressions}$ 复数的表示形式
代数形式（用于表示任意复数）：
\[z=x+\text{i}y\]三角形式（用于表示 非零 复数）：
\[z=r(\cos\theta+\text{i}\sin\theta)\]结合几何意义，这是显然的。
此时可以更直观地推导极坐标视角下的复数乘法：
\[\begin{align*} z_1z_2&=r_1(\cos\theta_1+\text{i}\sin\theta_1)\cdot r_2(\cos\theta_2+\text{i}\sin\theta_2)\\ &=r_1r_2(\cos\theta_1\cos\theta_2+\text{i}\sin\theta_1\cos\theta_2+\text{i}\cos\theta_1\sin\theta_2-\sin\theta_1\sin\theta_2)\\ &=r_1r_2[(\cos\theta_1\cos\theta_2-\sin\theta1\sin\theta_2)+\text{i}(\sin\theta_1\cos\theta_2+\cos\theta_1\sin\theta_2)]\\ &=r_1r_2(\cos(\theta_1+\theta_2)+\text{i}\sin(\theta_1+\theta_2)) \end{align*}\]依然根据 欧拉公式，可以引出 指数形式（用于表示 非零 复数）：
\[z=r\text{exp}(\text{i}\theta)\]$\text{Roots}$ 单位根
称 $x^n=1$ 在复数意义下的解是 $n$ 次复根，根据 代数基本定理，这样的解有 $n$ 个，称这 $n$ 个解都是 $n$ 次 单位根。
根据复数运算辐角相加的几何意义，很容易知道 $n$ 次单位根 $n$ 等分单位元。
设 $\omega_n=\text{exp }\frac{2\pi\text{i}}{n}$（即辐角为 $\frac{2\pi}{n}$ 的单位复数），则 $x^n=1$ 的解集表示为 ${\omega_n^k\mid k=0,1,\dots,n-1}$。
性质
$\text{OI-wiki}$ 上作为快速傅里叶变换（FFT）前置的三条性质以及我作为读者的自证不难证明。
- $\omega_n^n=1$
proof.
几何意义：相当于从单位复数 $w_n$ 出发，每次逆时针转动 $\frac{2\pi}{n}$ 的辐角，在单位圆上转了一圈。
代数证明如下：
\[\begin{align*} w_n^n&=(\text{exp }\frac{2\pi\text{i}}{n})^n\\ &=\text{exp}(2\pi\text{i})\\ &=\cos(2\pi)+\text{i}\sin(2\pi)\\ &=1 \end{align*}\]- $\omega_n^k=\omega_{2n}^{2k}$
几何意义：单位圆上以 $z=1$ 作为 $0$ 号等分点，分别作 $n$ 等分与 $2n$ 等分，从 $0$ 号等分点出发逆时针标号，$n$ 等分下的 $k$ 号等分点显然与 $2n$ 等分下的 $2k$ 号等分点重合。
代数证明如下：
\[\begin{align*} \omega_{2n}^{2k}&=(\text{exp }\frac{2\pi\text{i}}{2n})^{2k}\\ &=\text{exp }\frac{2k\pi\text{i}}{n}\\ &=(\text{exp }\frac{2\pi\text{i}}{n})^k\\ &=\omega_{n}^{k} \end{align*}\]- $w_{2n}^{k+n}=-w_{2n}^{k}$
几何意义：单位圆上以 $z=1$ 作为 $0$ 号等分点作 $2n$ 等分，$k+n$ 号等分点与 $k$ 号等分点关于实轴对称。
代数证明如下：
\[\begin{align*} \omega_{2n}^{n+k}&=(\text{exp }\frac{2\pi\text{i}}{2n})^{n+k}\\ &=\text{exp }\frac{2(n+k)\pi\text{i}}{2n}\\ &=\cos\frac{2(n+k)\pi}{2n}+\text{i}\sin\frac{2(n+k)\pi}{2n}\\ &=-(\cos\frac{2k\pi}{2n}+\text{i}\sin\frac{2k\pi}{2n})\\ &=-\text{exp }\frac{2k\pi\text{i}}{2n}\\ &=-(\text{exp }\frac{2\pi\text{i}}{2n})^k\\ &=-\omega_{2n}^{k} \end{align*}\]本原单位根
称集合：
\[\{\omega_n^k\mid 0\leq k< n,\gcd(n,k)=1\}\]中的元素为 $n$ 次 本原单位根。显然全体 $n$ 次本原单位根的集合大小为 $\varphi(n)$。
任意一个本原单位根 $w$ 对于任意 $0<k<n$，$\omega$ 的 $k$ 次幂不为 $1$。借助任何一个本原单位根，均可生成全体单位根。
$\text{Fast Fourier Transform}$ 快速傅里叶变换
$\text{Basic Idea}$ 基本思想
通过函数内积变换将原函数在 时域 上的卷积转换为变换后函数在 频域 上的乘积，反之亦然，进而可以通过傅里叶变换优化多项式乘法的时间复杂度。
这个说法相对抽象，在离散情况下，可以转换一种描述方式。将原序列 ${a_n}_{n=0}^{N-1}$ 视作多项式的 $0$ 到 $N-1$ 次方项 系数，根据拉格朗日插值法，确定 $N$ 个 点值 即可唯一确定这个多项式。离散傅里叶变换可以看作通过对点值的特殊选取，从而实现 系数表示法 与 点值表示法 之间的快速转换。
$\text{Fourier Transform}$ 傅里叶变换
设 $f(t)$ 是关于时间 $t$ 的函数，$F(\omega)$ 是关于频率 $\omega$ 的函数，傅里叶变换 表示为：
\[F(\omega)=\mathbb{F}[f(t)]=\int_{-\infty}^{\infty}f(t)e^{-\text{i}\omega t}dt\]其 逆变换 为：
\[f(t)=\mathbb{F}^{-1}[F(\omega)]=\frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega)e^{\text{i}\omega t}d\omega\]这不好理解但并不需要理解。
$\text{Discrete Fourier Transform}$ 离散傅里叶变换
离散傅里叶变换 DFT
设 ${x_n}_{n=0}^{N-1}$ 为某一满足有限性条件的序列，其 离散傅里叶变换（DFT） 定义为：
\[X_k=\sum_{n=0}^{N-1}x_ne^{-\text{i}\frac{2\pi}{N}kn}\]记为
\[\hat{x}=\mathcal{F}x\]根据前文所述的基本思想，离散傅里叶变换选择了 ${e^{-\text{i}\frac{2\pi}{N}k}}_{k=0}^{N-1}$ 这 $N$ 个坐标对应的点值表示原多项式，进一步地可以发现，所选取的这 $N$ 个点恰是 全体 $N$ 次单位根。
可以发现离散傅里叶变换 $\mathcal{F}$ 是一个 线性算子，因此可以构造出矩阵形式：
\[\left[\begin{matrix} X_0\\ X_1\\ \vdots\\ X_{N-2}\\ X_{N-1} \end{matrix}\right] = \left[\begin{matrix} 1&1&\cdots&1&1\\ 1&\alpha&\cdots&\alpha^{N-2}&\alpha^{N-1}\\ 1&\alpha^2&\cdots&\alpha^{2(N-2)}&\alpha^{2(N-1)}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 1&\alpha^{N-2}&\cdots&\alpha^{(N-2)(N-2)}&\alpha^{(N-2)(N-1)}\\ 1&\alpha^{N-1}&\cdots&\alpha^{(N-1)(N-2)}&\alpha^{(N-1)(N-1)} \end{matrix}\right] \left[\begin{matrix} x_0\\ x_1\\ \vdots\\ x_{N-2}\\ x_{N-1} \end{matrix}\right]\]其中 $\alpha=e^{-\frac{2\pi\text{i}}{N}}$。
离散傅里叶逆变换 IDFT
容易发现，以上方阵是一个 范德蒙德方阵，因此易证其行列式不等于 $0$，由此可以得出，离散傅里叶变换的逆变换（矩阵）存在。
我算了半天并没有算出来。
但是这是一个 范德蒙德方阵，结合单位复根的性质，直接有结论为：
\[\left[\begin{matrix} 1&1&\cdots&1&1\\ 1&\alpha&\cdots&\alpha^{N-2}&\alpha^{N-1}\\ 1&\alpha^2&\cdots&\alpha^{2(N-2)}&\alpha^{2(N-1)}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 1&\alpha^{N-2}&\cdots&\alpha^{(N-2)(N-2)}&\alpha^{(N-2)(N-1)}\\ 1&\alpha^{N-1}&\cdots&\alpha^{(N-1)(N-2)}&\alpha^{(N-1)(N-1)} \end{matrix}\right] \left[\begin{matrix} 1&1&\cdots&1&1\\ 1&\alpha^{-1}&\cdots&\alpha^{-(N-2)}&\alpha^{-(N-1)}\\ 1&\alpha^{-2}&\cdots&\alpha^{-2(N-2)}&\alpha^{-2(N-1)}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 1&\alpha^{-{N-2}}&\cdots&\alpha^{-(N-2)(N-2)}&\alpha^{-(N-2)(N-1)}\\ 1&\alpha^{-{N-1}}&\cdots&\alpha^{-(N-1)(N-2)}&\alpha^{-(N-1)(N-1)} \end{matrix}\right] =\left[\begin{matrix} N&0&0&\cdots&0&0\\ 0&N&0&\cdots&0&0\\ 0&0&N&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&N&0\\ 0&0&0&\cdots&0&N \end{matrix}\right]\]搬一个别人写的范德蒙德方阵逆矩阵的 计算过程。
看来还是我数学不太好。
根据矩阵形式容易得出，逆离散傅里叶变换（IDFT） 定义为：
\[x_n=\frac{1}{N}\sum_{k=0}^{N-1}X_ke^{\text{i}\frac{2\pi}{N}kn}\]记为：
\[x=\mathcal{F}^{-1}\hat{x}\]$\text{Fast Fourier Transform - I}$ 快速傅里叶变换 - 分治法
为了方便分治处理，默认多项式项数被补全到 $N=2^K(K\in\mathbb N_+)$。
FFT 的思想在于将奇次项与偶次项分开处理，此时奇次项提取公因子 $x$ 后又转换为了偶次项情况，进而形成两个子问题，达到分治效果。
如 $7$ 次多项式 $f(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+a_6x^6+a_7x^7$，按奇偶分为两组为：
\[\begin{align*} f(x)&=(a_0+a_2x^2+a_4x^4+a_6x^6)+(a_1x+a_3x^3+a_5x^5+a_7x^7)\\ &=(a_0+a_2x^2+a_4x^4+a_6x^6)+x(a_1+a_3x^2+a_5x^4+a_7x^6) \end{align*}\]利用奇偶次项的系数建立新的函数为：
\[G(x)=a_0+a_2x+a_4x^2+a_6x^3\\ H(x)=a_1+a_3x+a_5x^2+a_7x^3\]因此有：
\[f(x)=G(x^2)+xH(x^2)\]根据偶数次单位根性质 $\omega_n^i=-\omega_n^{i+n/2}$，$\omega_n^i$ 与 $\omega_n^{i+n/2}$ 对应的 $G(x^2)$ 值相同，$H(x^2)$ 值也相同。
因此有：
\[\begin{align*} f(\omega_n^k)&=G((\omega_n^k)^2)+\omega_n^k\cdot H((\omega_n^k)^2)\\ &=G(\omega_n^{2k})+\omega_n^k\cdot H(\omega_n^{2k})\\ &=G(\omega_{n/2}^k)+\omega_n^k\cdot H(\omega_{n/2}^k) \end{align*}\]同理：
\[\begin{align*} f(\omega_n^{k+n/2})&=G(\omega_n^{2k+n})+\omega_n^{k+n/2}\cdot H(\omega_n^{2k+n})\\ &=G(\omega_n^{2k})-\omega_n^k\cdot H(\omega_n^{2k})\\ &=G(\omega_{n/2}^k)-\omega_n^k\cdot H(\omega_{n/2}^k) \end{align*}\]根据以上推导，直接对 $G$ 和 $H$ 分治递归即可。
$\text{Fast Fourier Transform - II}$ 快速傅里叶变换 - 倍增法
位逆序置换
结论：每个系数最终位置的二进制表示为其初始二进制表示的左右翻转。
这个观察是显然的，每一次进行分组的根据都是当前子问题下的二进制最后一位（决定奇偶性），分组确定了从这次分组之后子问题内元素在子问题规模下的最高位（分到左边一组还是右边一组）。
考虑实现，如果从小到大枚举需要计算位逆序置换的数 $x$，置换后位置记为 $R(x)$。
显然计算 $R(x)$ 时，$R([\frac{x}{2}])$ 的值已知，因此可以得出递推式：
\[R(x)=[\frac{R([\frac{x}{2}])}{2}]+(x\bmod 2)\times\frac{N}{2}\]$N$ 的定义与前文相同。
蝶形运算优化
咕咕咕。
(没有这东西又不是不能做。)
$\text{Inverse Fast Fourier Transform}$ 快速傅里叶逆变换
由于傅里叶变换与傅里叶逆变换的在矩阵形式上的差别仅有两处：
- 两种变换矩阵所有对应位置的元素互为倒数。
- 傅里叶逆变换的结果需乘 $\frac{1}{N}$。
因此快速傅里叶逆变换的实现与快速傅里叶变换完全一致，只需对单位根取倒数后代入，最终结果除以 $N$ 即可。