任意模数 NTT

给定一个 $n$ 次多项式 $A$ 和一个 $m$ 次多项式 $B$，计算 $A \times B$，系数对 $p$ 取模。

$n,m \le 10^5$

做法

设

$$\begin{aligned} A0_i=\lfloor \frac {A_i}M \rfloor,A1_i=A_i \bmod M\\ B0_i=\lfloor \frac {B_i}M \rfloor,B1_i=B_i \bmod M \end{aligned}$$

于是

$$\begin{aligned} A = M \cdot A0 + A1\\ B = M \cdot B0 + B1 \end{aligned}$$

进一步

$$A \times B = M^2 \cdot A0 \cdot B0 + M(A0 \cdot B1 + A1 \cdot B0) + A1 \cdot B1$$

先对 $A0,A1,B0,B1$ 做一遍 DFT，求出 $A0 \times B0, A0 \times B1 + A1 \times B0,A1 \times B1$ 的点值表示后再分别 IDFT，共 $7$ 次。

注意系数可能达到 $10^{14}$，需要用 $w_n^k=\cos \frac {2k\pi}n+i \cdot \sin \frac {2k\pi}n$ 对 $w_n^k$ 进行预处理保证精度。

优化

下面考虑这样两件事：

• 现在要对实系数多项式 $A,B$ 进行 DFT。

  我们定义

  $$\begin{aligned} P = A + iB\\ Q = A - iB \end{aligned}$$

  推导可以得到一个很优美的结论：

  $$\text {conj}(Q(w_n^k))=P(\text{conj}({w_n^{k}}))$$

  于是只需一次 DFT 就可以求出 $A,B$ 的点值表示。

• 现在已知实系数多项式 $A,B$ 的点值表示 $A',B'$，要求 $A,B$。

  我们定义

  $$P = A' + iB'$$

  对 $P$ 进行 IDFT 得到 $P'$，于是

  $$P' = A + iB$$

  因此 $P'$ 的实数部分就是 $A$, 虚数部分就是 $B$。

  于是只需一次 IDFT 就可以达到对 $A',B'$ 分别做 IDFT 的效果.

将 $7$ 次 DFT 两两配对可以合并成 $4$ 次 DFT。

代码

参考资料

国家集训队 2016 论文集，《再探快速傅里叶变换》毛啸。