fft 和 ntt 和多项式基础操作

panyf · 2022-05-28 11:22:51 · 个人记录

FFT

根据拉格朗日插值的构造我们知道，n+1 个点值可以唯一表示一个 n 次多项式。考虑如何快速计算两个多项式的乘法。点值的乘法是容易的，直接将 x 相同的点值相乘即可。但是系数转点值（直接对每个 x O(n) 求值）和点值转系数（拉格朗日插值），常规的做法都需要 O(n^2) 的复杂度。

fft 通过选取特殊的 x，能够做到 O(n\log n) 进行点值和系数的转换。求出最小的 n=2^k 大于多项式次数，将多项式的次数补到 n-1 次，选取 n 个 x，分别是方程 x^n=1 的 n 个根，称为 n 次单位根（根据定义这些 x 互不相同）。记 \omega_n=e^{2\pi i/n}=cos(2\pi/n)+isin(2\pi/n)，这 n 个根依次为 \omega_n^0,\omega_n^1\cdots\omega_n^{n-1}。

单位根的性质：\omega_n^n=1，\omega_n^k=\omega_{2n}^{2k}，\omega_{2n}^{n+k}=-\omega_{2n}^k。根据定义显然。

对于一个 2n-1 次多项式 f(x)=a_0+a_1x+\cdots+a_{2n-1}x^{2n-1}。记 g(x)=a_0+a_2x+\cdots+a_{2(n-1)}x^{n-1}，h(x)=a_1+a_3x+\cdots+a_{2(n-1)+1}x^{n-1}。有 f(x)=g(x^2)+h(x^2)x。根据单位根的性质，f(\omega_{2n}^k)=g(\omega_n^k)+\omega_{2n}^kh(\omega_n^k),f(\omega_{2n}^{k+n})=g(\omega_n^k)-\omega_{2n}^kh(\omega_n^k)，于是求出 g(\omega_n^k) 和 h(\omega_n^k)，就可以 O(n) 求出 f(\omega_{2n}^k)。T(n)=2T(n/2)+O(n)=O(n\log n)。

递归 fft 太慢，考虑优化常数。考虑一个多项式的系数 \{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。发现最终位置 i 的值对应原序列位置 r_i 的值，其中 r_i 是 i 的二进制位翻转（比如 "1011" 变成 "1101"）之后的结果。其实很好理解，第一层就是按最低位分成左右两半，第二层就是在上一次的基础上按次低位分成两半，依次类推，于是比较两个数的最终位置就是从低位到高位比较。O(n) 递推 r：首先 r_0=0。对于 r_i，若最低位为 0，就是 r_{i/2}/2；否则在最高位补一个 1，就是 r_{\lfloor i/2 \rfloor}/2+n/2。通过 a_i 求出 a_{r_i}：注意到 r_i=j 则有 r_j=i，所以只需要枚举 i，若 i<r_i 则交换 a_i 和 a_{r_i}，这样就实现原地 O(n) 转化。

然后就是系数转点值了。考虑从深层开始倒着做，枚举 i 表示当前层要将两个长度为 i 的多项式的答案合并（每层的 i 是下一层乘 2），枚举 2i 的倍数 j 表示要合并的两部分对应原序列的位置 [j,j+2^i-1],[j+2^i,j+2^{i+1}-1]，再枚举 k\in[0,i) 表示合并 j+k 和 i+j+k。于是有 a'_{j+k}=a_{j+k}+\omega_{2i}^k a_{i+j+k},a'_{i+j+k}=a_{j+k}-\omega_{2i}^ka_{i+j+k}，a 表示原来的答案，a' 表示合并后的答案。复杂度 O(n\log n)。

考虑如何点值转系数。对求出的 n 个点值再跑一遍 fft，位置 i 的值即为 \sum_{k\in[0,n)} (a_k\sum_{j\in[0,n)} (\omega_n^{i+k})^j)。注意到 \sum_{j\in[0,n)}w_n^{xj} 在 x=0 的时候值为 n，在 x\in(0,n) 的时候值为 0。于是位置 0 的值为 na_0，位置 i>0 的值为 na_{n-i}。对序列的位置 [1,n) 翻转，然后每个位置除以 n 即可。

NTT

ntt 在模某些特殊整数下进行系数和点值转换。以常见模数 P=998244353 为例，有 \varphi(P)=P-1，P-1=7\times 17\times 2^{23}。并且 P 存在原根（一个数 x 的原根 g 满足性质：最小的正整数 y 使得 g^y\equiv 1(\bmod x)，有 y=\varphi(x)），最小的原根是 3。

考虑找到一个单位根的替代品。取 \omega_n=g^{(P-1)/n}，容易发现其满足单位根的几条性质。通过这种构造，当 n 不超过 2^{23} 时，可以直接进行模 998244353 的系数和点值转换。

分治 FFT

1.求若干个多项式的乘积，次数和不超过 n。

做法 1：用堆维护多项式次数，每次取次数最小的两个多项式乘起来（类似合并果子）。

做法 2：直接分治，考虑要求区间 [l,r] 的多项式乘积，求出中点 m，求出 [l,m],[m+1,r] 的乘积，然后乘起来。

两种做法本质没啥区别，复杂度都是 O(n\log^2 n)（因为最优二叉树和分治树深度都是 \log n，每层复杂度 O(n\log n)）。

2.半在线卷积。模板题：P4721 【模板】分治 FFT。

考虑 cdq 分治，求出 f_{[l,m]}，对 f_{[m+1,r]} 的贡献就是 f_{[l,m]} 乘上 g_{[0,r-l]} 之后 [m+1,r] 这部分的系数，可以用 fft 优化。复杂度 T(n)=2T(n/2)+O(n\log n)=O(n\log^2 n)。

MTT

任意模数（大概 10^9 级别）的多项式乘法。不能直接用 fft 因为会爆精度。

先咕了，见P4245 题解。

多项式基础操作

求逆

给定 n-1 次多项式 f(x)，求 g(x) 满足 f(x)g(x)=1。以下默认只需要求 g(x) 的前 n 项。

存在逆需要满足 [x^0]f(x)\neq 0。