NTT

NTT ，快速数论变换，功能与 FFT 完全一致，用来求多项式卷积。
NTT 优点在于常数稍微小一点，没有精度误差。
但是 NTT 系数必须是取模意义下的整数，且对模数有特殊要求。

FFT 的单位根

建议前置 FFT 。

FFT 可以分治优化复杂度的原因是用到了单位根的如下性质：
\[ W_{2n}^{2k} = W_n^k \] \[ W_n^n = 1 \] \[ W_n^{k + n/2} + W_n^k = 0 \]

可是用单位根做 FFT ，需要用到复数和浮点数，常数大而且有精度误差。
还有别的数有这样的性质来替换单位根吗？
遗憾的是，可以证明复数域下只有单位根有这样的性质。

取模

实际计算多项式卷积时，常常要求对系数取模以避免不必要的麻烦。
那么这时候系数实际上是在模意义下的， FFT 将它转到复数域上运算，似乎没有必要。
模意义下什么数可以有单位根那样的性质？
有的，那就是原根。

原根

对于某些模数 P ，模 P 意义下的原根 g 满足：
对任意 $ 0 k P - 2 $ ， $ g^k $ 互不相同。 有些模数可能不存在原根，这里先假设模数都有原根。

假设系数是模 P 意义下的，P 是形如 $ 2^k + 1 $ 的质数，其原根为 g ，
设 $ G_n = g^{} mod P $ ，其中 n 是小于 P 的 2 的整次幂 。
那么在模 P 意义下， G 满足：

\[ G_{2n}^{2k} = G_n^k \]

由 G 定义可证：
$ G_{2n}^{2k} = g^{2k} = g^{k} = G_n^k$

\[ G_n^n = 1 \]

由 G 定义可得：
$ G_n^n = g^{n} = g^{P-1} $
由费马小定理：
$ G_n^n = g^{P-1} = 1 $

\[ G_n^{k + n/2} + G_n^k = 0 \]

有第一条性质可得：
$ G_n^{n/2} = G_2^1 = g^{} $
因为 $ (g^{})2 = g^{P-1} = 1 $
根据原根的性质：
$ g^{} g^{P-1} $
那么 $ g^{} = -1 $ （即 P - 1）。
那么可以证得：
$ G_n^{k + n/2} = G_n^k G_n^{n/2} = G_n^k(-1) $
于是 $ G_n^{k + n/2} + G_n^k = 0 $

NTT

于是 NTT 的算法思路就呼之欲出了：把 $ W_n $ 全部替换为 $ G_n $ 即可。
这样就可以算出模 P 意义下的多项式卷积了。
其中 n 必须是 2 的整次幂，不足的补零即可。

现在唯一的问题是，模数 P 要满足什么条件，以及如何求模 P 意义下的原根 g 。
然而我并不想深入展开，大多数情况下模数都是 998244353 ，其原根为 3 。
一般 NTT 只会用这个模数，不会有毒瘤出题人卡这个模数的（我不对这句话负责）。