FFT、NTT小结

这种东西还是写一点比较重要的思路和式子之类的放在这里比较好,毕竟过一段时间估计就会忘。。。

其实并不太建议初学者看这篇文章,因为它真的只是备忘用的,很多东西都写的比较简单。。。

特别详细的解释可以戳这里,这篇文章是真\cdot小学生都看得懂

FFT(快速傅里叶变换)

主要流程是选取一些合适的点值,通过DFT变换,把多项式由系数表示法转化为点值表示法,直接把两个多项式对应点值相乘,再通过IDFT转化回点值表示法。整个算法在O(nlogn)O(n\log n)的时间复杂度内完成了两个多项式的卷积

单位复数根

ωn=1\omega^n=1,则ω\omegann个解,把复平面上的单位圆分成nn等分

定义ωn\omega_{n}为最小的那个解,也就是从(1,0)(1,0)开始逆时针方向第一个解

那么ωni(i[0,n1])\omega_n^i(i\in [0,n-1])就表示出了这nn个解,其中ωn0\omega_{n}^{0}表示(1,0)(1,0)

  • 如何求ωn\omega_{n}呢?

    这个东西本质上就是单位圆上一个nn等分点的坐标,显然就是(cosθ,sinθ)(\cos\theta, \sin\theta),也就是(cos2πn,sin2πn)(\cos{\frac{2\pi}{n}}, \sin{\frac{2\pi}{n}})。这个东西根本不需要什么欧拉公式去求


有一些关于这个东西的性质:

  • ωni+n=ωniωnn=ωni\omega_{n}^{i+n}=\omega_{n}^{i}*\omega_{n}^n = \omega_n^i

  • 消去引理:ωdndk=ωnk\omega_{dn}^{dk}=\omega_{n}^k

  • 折半引理:ωnk+n2=ωnk\omega_{n}^{k+\frac{n}{2}}=-\omega_{n}^k

    上面这两个都可以利用单位圆很显然地发现

  • 求和引理:对于任意整数n1n\le1和不能被nn整除的kk,有j=0n1(ωnk)j=0\sum\limits_{j=0}^{n-1}(\omega_{n}^{k})^j=0

    这个可以用等比数列求和证明

这些引理在下面化式子的时候都会用到

DFT

我们选wnkw_{n}^k来求点值,即要求A(ωnk)(k[0,n1])A(\omega_{n}^{k})~ (k\in[0, n-1])

把多项式A(x)A(x)按下标奇偶性划分成两个部分:

A(x)=(a0+a2x2+a4x4+...+an2xn2)+(a1x+a3x3+a5x5+...+an1xn1)A(x) = (a_0+a_2x^2+a_4x^4+...+a{n-2}x^{n-2})+(a_1x+a_3x^3+a_5x^5+...+a_{n-1}x^{n-1})

那么有

A(x)=A1(x2)+xA2(x2)A(x) = A_1(x^2) + xA_2(x^2)

假设现在我们要求A(ωnk),k[0,n2]A(\omega_{n}^k),k\in[0, \frac{n}{2}]

A(ωnk)=A1(ωn2k)+ωnkA2(ωn2k)=A1(ωn2k)+ωnkA2(ωn2k)\begin{aligned} A(\omega_{n}^k) &= A_1(\omega_{n}^{2k})+\omega_n^kA_2(\omega_n^{2k})\\ &=A_1(\omega_{\frac{n}{2}}^k)+\omega_{n}^kA_2(\omega_{\frac{n}{2}}^k) \end{aligned}

A(ωnk+n2)=A1(ωn2k+n)+ωnk+n2A2(ωn2k+n)=A1(ωn2k)ωnkA2(ωn2k)=A1(ωn2k)ωnkA2(ωn2k)\begin{aligned} A(\omega_{n}^{k+\frac{n}{2}}) &= A_1(\omega_{n}^{2k+n})+\omega_n^{k+\frac{n}{2}}A_2(\omega_n^{2k+n})\\ &=A_1(\omega_{n}^{2k})-\omega_n^{k}A_2(\omega_n^{2k})\\ &=A_1(\omega_{\frac{n}{2}}^{k})-\omega_{n}^kA_2(\omega_{\frac{n}{2}}^k) \end{aligned}

于是我们就可以通过分治递归,利用A1(ωn2k)A_1({\omega_{\frac{n}{2}}^{k}})A2(ωn2k)A_2({\omega_{\frac{n}{2}}^{k}})来求出A(ωn2k)A({\omega_{\frac{n}{2}}^{k}})

复杂度O(nlogn)O(n \log n)

IDFT

IDFT的结论用上面提到的求和引理和一系列的化式子(或者用矩阵)可以证明,但在这里并不想写了

结论就是做一遍DFT,其中ωn\omega_{n}改为ωn1\omega_{n}^{-1},然后最后乘1n\frac{1}{n}

二进制翻转

发现在做DFT的时候需要把奇数偶数下标分开算,再合并起来。 不过直接这么做会很慢,考虑把数组直接按照最后的形态分奇偶排好。

(a0,a1,a2,a3,a4,a5,a6,a7)(a0,a2,a4,a6)(a1,a3,a5,a7)(a0,a4)(a2,a6)(a1,a5)(a3,a7)(a0)(a4)(a2)(a6)(a1)(a5)(a3)(a7)\begin{aligned} &(a_0, a_1, a_2, a_3, a_4, a_5, a_6, a_7)\\ &(a_0, a_2, a_4, a_6)(a_1, a_3, a_5, a_7)\\ &(a_0, a_4)(a_2, a_6)(a_1, a_5)(a_3, a_7)\\ &(a_0)(a_4)(a_2)(a_6)(a_1)(a_5)(a_3)(a_7) \end{aligned}

通过观察发现,最后的每个位置的数字恰好就是原数字在二进制下按位反转的结果。

感性理解一下,每次重新划分相当于是按照最低位为0还是1分的,为0则会分到前面一半(最高位为0),为1则会分到后面一半。因此最后就是原数二进制反转的结果

注意到这一点后,就可以直接处理出这个置换数组rev[]rev[]了:

1
rev[i] = (rev[i >> 1] >> 1) + (i & 1 ? n >> 1 : 0)

这个相当于看ii二进制最低位是什么

NTT(快速数论变换)变换

考虑在模意义下卷积,也就是卷出来的系数要对某个数取模

一般而言,模数要是2ab+12^ab+1的形式,其中2a2^a要不小于n

我们需要找到在模意义下什么东西具有单位复数根ωn\omega_{n}的性质

答案是原根gg,通常使用的998244353998244353的原根g=3g=3

由于gmod1=1g^{mod-1} = 1,我们就可以用gmod1pg^{\frac{mod-1}{p}}来代替ωn\omega_{n}

不难证明原根也有单位复数根的那些性质

分治FFT

假设我们有一个长这样的递推式:f(n)=i=0i1f(i)g(ni)f(n) = \sum\limits_{i=0}^{i-1}f(i)g(n-i)

和CDQ分治、分治优化Dp的思想类似,其实就是考虑跨中点的贡献

先递归求[l,mid][l, mid]的答案,此时[l,mid][l,mid][mid+1,r][mid + 1, r]的贡献长这样:f(x)=i=lmidf(i)g(xi),x[mid+1,r]f(x) = \sum\limits_{i=l}^{mid}f(i)g(x-i),x\in[mid + 1, r]

[l,mid][l, mid]ffgg卷起来,算出所有[l,mid][l,mid]的值对于[mid+1,r][mid+1, r]中每个位置对应的贡献,最后递归计算[mid+1,r][mid + 1, r]的答案

需要注意的是,必须先递归左边,求出答案并算完左边对右边的贡献后,再递归右边,原因比较显然

这个算法常数比较大,有时可以区间长度小于某个值(如20)就暴力计算

感谢你的赞赏!