最近在各种比赛中做了一些关于FFT的题目，感觉对FFT的理解还不是特别深刻，于是在网上搜了一些资料，整理出了关于DFT（FFT）和NTT的一些内容。
DFT
我们都知道，当我们用到FFT或者NTT的时候，都是各种多项式乘法的内容，于是问题来了，为什么它是对的？
先从线代的内容开始
考虑这样一个矩阵：
\[A = \left( \begin{matrix} a_{0,0} & a_{0,1} & \cdots & a_{0,n-1} \\ a_{1,0} & a_{1,1} & \cdots & a_{1,n-1} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n-1,0} & a_{n-1,1} & \cdots & a_{n-1,n-1} \\ \end{matrix} \right)\]和这样一个向量 $x = \left(x_0, x_1, \cdots, x_{n-1}\right)^T$
如果它是线性无关的，且是可逆的，那么我们就有$AxA^{-1} = x$，我们发现这是一句废话，所以并没有多少实用价值。但是我们这时候就把$A$这个矩阵叫做变换好了。
我们知道，DFT的目的是为了做向量的卷积，即求出 $z = x \star y$ , 这里 $\star$ 表示卷积。
如何利用上面这些东西？
注意到 $z_v = \sum_{q} x_q y_{v-q}$
我们又注意到 $(Ax)_{u} =\sum_qx_qa_{u,q}$ 和 $(Ay)_{u} = \sum_q y_q a_{u,q}$
$(Ax)_{u} (Ay)_{u} = \sum_p\sum_q x_p y_q a_{u,p} a_{u,q}$
那么这个时候，如果我们在$z$边上加个求和符号的话，就得到了
\[\sum_v z_v = \sum_p \sum_q x_q y_{p-q} = \sum_q x_q \sum_q y_{q} = (\sum_q x_q)(\sum_q y_{q})\]那么如果再在左边加上一个 $a_{u,v}$ 呢？
\[Z_u = \sum_v z_v a_{u,v} = \sum_p \sum_q x_q y_{p-q} a_{u,v}\]啊，如果对于矩阵$A$，我们有 $a_{u,p}a_{u,q} = a_{u,p+q}$ 的话就好了，因为这样我们就可以得到一个重要的式子——
$Az = Ax \cdot Ay$
证明
由前文得到的
\[Z_u = \sum_v z_v a_{u,v} = \sum_p \sum_q x_q y_{p-q} a_{u,v}\]我们有
\[Z_u = \sum_v z_v a_{u,v} = \sum_p \sum_q x_q y_{p-q} a_{u,q}a_{u,p-q}\]即
\[Z_u = \sum_q x_q a_{u,q} \sum_p y_{q,p-q} a_{u,p-q} = (Ax)_u (Ay)_u\]即
\[Z = (Ax)\cdot (Ay)\]即
\[Az = (Ax)\cdot (Ay)\]于是呢？
根据指数函数的性质，我们可以轻易构造出一组$A_{u,v} = b_u^v$异或
构造
\[A = \left( \begin{matrix} 1 & b_0 & b_0^2 & \cdots & b_0^{n-1} \\ 1 & b_1 & b_1^2 & \cdots & b_1^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & b_2 & b_2^2 & \cdots & b_{n-1}^{n-1} \\ \end{matrix} \right)\]当$b_u$两两不同的时候，$A$是可逆的。
性质
从上面这些内容，我们可以得出这个变换的一些性质：
- $Ax + Ay = A(x + y)$
- $A(kx) = kAx$
- $x\star y\star z = Ax \cdot Ay \cdot Az$ 推广得到 ${\Large\star} x_i = {\Large\cdot}Ax_i$
- $(x_1 + x_2)\star y = (Ax_1 + Ax_2)\cdot Ay$（我们将在后面展示这个性质的应用）
这里的第一、二条很显然，第三条要理解这个变换的实质，而第四条则是第1条的另一个扩展，它在部分情况下很实用。
从 DFT 到 FFT
现在思考我们在DFT中用到的矩阵
\[A = \left( \begin{matrix} 1 & b_0 & b_0^2 & \cdots & b_0^{n-1} \\ 1 & b_1 & b_1^2 & \cdots & b_1^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & b_{n-1} & b_{n-1}^2 & \cdots & b_{n-1}^{n-1} \\ \end{matrix} \right)\]发现要计算它还是得 $O(n^2)$ 的时间，我们觉得很恶心，因为这样的变换没有起到降低复杂度的作用。于是我们考虑一个我们已经用过很多遍的技术……算贡献。
然而我们发现……并没有什么卵用。这时候就有人提出，如果让$b_k = b_1^n$的话，事情似乎会变得不一样……
\[A = \left( \begin{matrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & b & b^2 & \cdots & b^{n-1} \\ 1 & b^2 & b^4 & \cdots & b^{2(n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & b^{n-1} & b^{2(n-1)} & \cdots & b^{(n-1)^2} \\ \end{matrix} \right)\]我们发现它依然是可逆的，但是依然没有什么卵用，考虑令 $b = e^{2\pi / n}$
\[A = \left( \begin{matrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & e^{2\pi / n} & e^{2\times 2\pi / n} & \cdots & e^{(n-1)\times 2\pi / n} \\ 1 & e^{2\times 2\pi / n} & e^{4\times 2\pi / n} & \cdots & e^{(n-2)\times 2\pi / n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & e^{(n-1)\times 2\pi / n} & e^{(n-2)\times 2\pi / n} & \cdots & e^{2\pi / n} \\ \end{matrix} \right)\]不妨令 $n=8$，我们直观感受一下这个矩阵。
\[A = \left( \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & e^{1\times 2\pi / 8} & e^{2\times 2\pi / 8} & e^{3\times 2\pi / 8} & e^{4\times 2\pi / n} & e^{5\times 2\pi / 8} & e^{6\times 2\pi / 8} & e^{7\times 2\pi / 8} \\ 1 & e^{2\times 2\pi / 8} & e^{4\times 2\pi / 8} & e^{6\times 2\pi / 8} & 1 & e^{2\times 2\pi / 8} & e^{4\times 2\pi / 8} & e^{6\times 2\pi / 8} \\ 1 & e^{3\times 2\pi / 8} & e^{6\times 2\pi / 8} & e^{1\times 2\pi / 8} & e^{4\times 2\pi / 8} & e^{7\times 2\pi / 8} & e^{2\times 2\pi / 8} & e^{5\times 2\pi / 8} \\ 1 & e^{4\times 2\pi / 8} & 1 & e^{4\times 2\pi / 8} & 1 & e^{4\times 2\pi / 8} & 1 & e^{4\times 2\pi / 8} \\ 1 & e^{5\times 2\pi / 8} & e^{2\times 2\pi / 8} & e^{7\times 2\pi / 8} & e^{4\times 2\pi / 8} & e^{1\times 2\pi / 8} & e^{6\times 2\pi / 8} & e^{3\times 2\pi / 8} \\ 1 & e^{6\times 2\pi / 8} & e^{4\times 2\pi / 8} & e^{2\times 2\pi / 8} & 1 & e^{6\times 2\pi / 8} & e^{4\times 2\pi / 8} & e^{2\times 2\pi / 8} \\ 1 & e^{7\times 2\pi / 8} & e^{6\times 2\pi / 8} & e^{5\times 2\pi / 8} & e^{4\times 2\pi / 8} & e^{3\times 2\pi / 8} & e^{2\times 2\pi / 8} & e^{1\times 2\pi / 8} \\ \end{matrix} \right)\]折半引理和蝶形变换
注意到 $b^k = b^{\lfloor k / 2\rfloor}b^{k - 2\lfloor k / 2\rfloor}$ ，我们发现这又是一句废话，但是它非常有用。
然后继续观察矩阵的特征，考虑使用 $X^{[0]}$ 和 $X^{[1]}$ 分别表示这个矩阵分别作用于$x$偶数行和$x$的奇数行的结果。则我们发现，对于结果的前4行，我们有 $X_k = X_k^{[0]} + X_k^{[1]}$ ，对于结果的后四行，我们有 $X_{k+4} = X_{k+4}^{0} - X_{k+4}^{[1]}$
考虑这样的一个计算方法：
\[\begin{matrix} X^{[0]} =& x_0 + b^2x_2 + b^4x_4 + b^6x_6 + \ldots + b^{2n}x_{2n}\\ X^{[1]} =& b(x_1 + b^2x_3 + b^4x_5 + b^6x_7 + \ldots + b^{2n}x_{2n+1}) \end{matrix}\]注意到这个过程可以递归分治实现，故复杂度为 $O(n \log n)$ ，进一步的分析可以使用非递归的FFT进行计算。
(哇，这又是行又是列的真是绕)
从DFT到NTT
注意到在DFT中，我们使用了单位复数根$e^{2\pi / n}$作为我们的$b$，那么如果要求使用整数，或者说模 $p$ 的群中进行计算的话，有没有别的方法可以达到一样的效果呢？
注意到我们需要这个数满足下面的性质：
- $b^{i}$，当$k$取 $i$ 到 $n - 1$ 的时候，值不能有重复。这是为了保证矩阵的线性无关。
- $b^{i} + b^{i + n/2} = 0$ ，当然这一点很好满足，因为我们只需要让 $b^{n} = 1 (\mod p)$，即可满足这一点。
那么答案当然是存在的，利用数学中原根的概念，可以很轻易做到这一点。
那么问题就变得非常简单了，只需要简单地用 $p$ 的乘法原根去替换前文中的 $b$ ，我们就可以得到一个新的变换，同时它还满足FFT的几乎所有性质。我们管他叫NTT
（完，这篇文章主要讲了FFT和NTT的各种“为什么”，也是我一直以来比较疑惑的一点。）