快速数论变换（NTT）

将快速傅里叶变换（FFT）中的单位根换成原根，就成了快速数论变换（NTT）。NTT 没有精度误差，但是 NTT 要求系数为整数，且要对特殊的质数取模（设这个质数是 $p$，且 $p=r \times 2^k+1$，$2 \not | r$，$k \in \mathbb{N}$，那么它只能用来处理乘积的最高次数 $<2^k$ 的多项式乘法）。

引入

回顾 FFT 中用到的 $\omega$ 的性质：

1. $\omega_n^n=1$；
2. $\omega_n^0,\omega_n^1,\omega_n^2,\cdots,\omega_n^{n-1}$ 两两不等，可以还原出系数；
3. 当 $n$ 为偶数时，$\omega_n^2=\omega_{n \div 2}$，$\omega_n^{n \div 2+k}=-\omega_n^k$，按照指数奇偶分类之后能够把带入的值也减半使得问题规模能够减半；
4. $\sum\limits_{k=0}^{n-1}(\omega_n^{j-i})^k=n \times [i=j]$，能够用相同的方法进行逆变换得到系数表示。

可以使用原根代替单位根来实现 FFT，简称 NTT。

根据费马小定理，对于一个素数 $p$，有如下关系：$a^{p-1} \equiv 1 \pmod p$。

概念：原根。$p$ 的原根 $g$ 定义为使得 $g^0 \bmod p,g^1 \bmod p,\cdots,g^{p-2} \bmod p$ 互不相同的数。

取素数 $p=k \times n+1$，其中 $n$ 为 $2$ 的正整数次幂，$k \in \mathbb{N}^*$，原根为 $g$，令 $g_n \equiv g^k \pmod p$，这样就可以满足 $g_n^0 \bmod p,g_n^1 \bmod p,\cdots,g_n^{n-1} \bmod p$ 互不相同，并且 $g_n^1 \equiv 1 \pmod p$，满足性质 1、2。

由于 $p$ 是素数，并且 $g_n^n \equiv 1 \pmod p$，这样 $g_n^{\frac{n}{2}}$ 必然是 $-1$ 或 $1$。再根据互不相同这个特点，$g_n^{\frac{n}{2}} \equiv -1 \pmod p$，满足性质 3。

代码实现

模板题：Luogu P3803

递归版

提交记录 备份

迭代版

提交记录 备份

封装代码

递归版

提交记录 备份

迭代版

提交记录 备份

高度封装代码

迭代版

提交记录 备份

提交记录 备份

任意模数 NTT：MTT

若题目给出的模数 $P$ 不存在原根，可以估计一下答案的范围（一般为 $n \times \max\{a_i\}^2$，在 $[0,10^{23}]$ 范围内），可以求出答案对三个大质数的模，再用中国剩余定理合并。

模板题：Luogu P4245。

普通版

提交记录 备份

高度封装版

提交记录 备份

如果要包装 mod_int，不同模数之间的运算需要处理。

提交记录 备份

原根表

此表格来自 FFT用到的各种素数 – Miskcoo's Space（现在已经不可查看），Wayback Machine。

例题