FFT mod 1e9 + 7

在做FFT mod 任意质数一个传统的方法是利用NTT和CRT,这样比较适合一些小模数的题目,因为要保证$NP^2$在64位整数范围内,不然将需要更高精度的整数。

但最近学习了一种比较Tricky的方法,假设模数为$P$,设$M=\lceil \sqrt{P} \rceil$,可以将一个多项式$F(x)$拆成两个多项式$F_{0}(x),F_{1}(x)$,其中:

这样就能把多项式每一项系数的值域变成$\sqrt{P}$级别,用double实现的复数做FFT精度就不会爆炸了。

如果要求两个多项式$F(x),G(x)$的卷积:

这样只需似乎只用做7次FFT,效率应该比NTT要好,然而这只是一个开始。

由于这里需要用复数的FFT来做整数的卷积,可以使用一些技巧来继续减少 FFT 的次数。

比如如果需要对$A$和$B$分别做一次DFT,可以构造两个多项式:

不难证明 $DFT(Q)[i] = DFT(P)[n - i]$,$n$ 是 DFT 的规模,所以只需要对 $P$ 做一次 DFT,就能一块求出 $Q$ 的 DFT。

然后 $DFT(A) = \frac{DFT(P) +DFP(Q)}{2} , DFT(B) = -\frac{DFT(P) - DFT(Q)}{2}i$。

这样只需 FFT 2 次就能计算出$F_{0}(x),F_{1}(x), G_{0}(x),G_{1}(x)$ 的 DFT 。

IDFT 也是同理,虽然 IDFT 前的结果是复数,但是 IDFT 后的结果都是整数,所以也能使用上述的技巧将 IDFT 的次数从 3 次减少到 2 次,从而就得到了只需 FFT 4 次的任意模数的卷积运算。