跳转至

FFT & NTT 复习笔记

默认文中的形如 [l,r)[l,r) 的区间为其与整数集的交集。

快速变换

设原多项式为 F(x)=∑i∈[0,n)aixiF(x) = \sum_{i \in [0,n)} a_i x ^ i，其中 n=2k,k∈Z+n = 2 ^ k, k \in \mathbb Z ^ +。

我们要求 ∀i∈[0,n),a^i=F(ti)\forall i \in [0,n),\hat a_i = F(t_i)，其中 tt 是一个长度为 nn 且两两互不相同的序列。

显然 FF 可以被一组 a^,t\hat a,t 唯一确定，即点值表示法。

另设两个多项式

G0(x)=a0+a2x+⋯+an−2xn2−1G1(x)=a1+a3x+⋯+an−1xn2−1 G_0(x)=a_0 + a_2 x + \dots + a_{n - 2} x^{\frac n 2 - 1} \\ G_1(x)=a_1 + a_3 x + \dots + a_{n - 1} x^{\frac n 2 - 1} \\

则有

F(x)=∑i∈[0,n)aixi=a0+a1x+a2x2+⋯+an−1xn−1=(a0+a2x2+⋯+an−2xn−2)+(a1x+a3x3+⋯+an−1xn−1)=G0(x2)+xG1(x2) \begin{aligned} F(x) & = \sum_{i \in [0,n)} a_i x ^ i \\ & = a_0 + a_1 x + a_2 x^2 + \dots + a_{n-1} x^{n-1} \\ & = (a_0 + a_2 x^2 + \dots + a_{n-2} x^{n-2}) + (a_1 x + a_3 x^3 + \dots + a_{n-1} x^{n-1}) \\ & = G_0 (x ^ 2) + x G_1 (x ^ 2) \\ \end{aligned}

考虑构造单位根 ωnk\omega _n ^k 满足 ωnn2=−1,ω2n2k=ωnk\omega _n ^{\frac n 2} = -1, \omega _{2n} ^ {2k} = \omega _n ^k。

显然也有 ωnn=ωn0=1\omega _n ^n = \omega _n ^0 = 1。

设 ∀i∈[0,n),ti=ωni\forall i \in [0,n), t_i = \omega _n ^i。

当 x=ωnk,k∈[0,n2)x = \omega _n ^k, k \in [0,\frac n 2) 时显然有

F(ωnk)=G0(ωn2k)+ωnkG1(ωn2k)=G0(ωn2k)+ωnkG1(ωn2k) \begin{aligned} F(\omega _n ^k) & = G_0(\omega _n ^{2k}) + \omega _n ^k G_1(\omega _n ^{2k}) \\ & = G_0(\omega _ {\frac n 2} ^ k) + \omega _n ^k G_1(\omega _{\frac n 2} ^k) \\ \end{aligned}

当 x=ωnk+n2,k∈[0,n2)x = \omega _n ^{k + \frac n 2}, k \in [0,\frac n 2) 时有

F(ωnk+n2)=G0(ωn2k+n)+ωnk+n2G1(ωn2k+n)=G0(ωn2k⋅ωnn)−ωnkG1(ωn2k⋅ωnn)=G0(ωn2k)−ωnkG1(ωn2k)=G0(ωn2k)−ωnkG1(ωn2k) \begin{aligned} F(\omega _n ^{k + \frac n 2}) & = G_0(\omega _n ^{2k + n}) + \omega _n ^{k + \frac n 2} G_1(\omega _n ^{2k + n}) \\ & = G_0(\omega _n ^{2k} \cdot \omega _n ^n) - \omega _n ^k G_1(\omega _n ^{2k} \cdot \omega _n ^n) \\ & = G_0(\omega _n ^{2k}) - \omega _n ^k G_1(\omega _n ^{2k}) \\ & = G_0(\omega _{\frac n 2} ^k) - \omega _n ^k G_1(\omega _{\frac n 2} ^k) \\ \end{aligned}

由于两者只有一个符号的差异，于是 FF 的点值可以直接 O(n)\mathrm O(n) 从 G0,G1G_0, G_1 的点值得到。

递归解决，时间复杂度 O(nlog⁡n)\mathrm O(n \log n)。

逆变换

设变换后的点值序列为 a^\hat a，即

∀i∈[0,n),a^i=F(ωni)=∑j∈[0,n)aj(ωni)j=∑j∈[0,n)ajωnij \begin{aligned} \forall i \in [0,n), \hat a_i & = F(\omega _n ^i) \\ & = \sum _{j \in [0,n)} a_j (\omega _n ^i)^j \\ & = \sum _{j \in [0,n)} a_j \omega _n ^{ij} \\ \end{aligned}

设多项式 F^(x)=∑i∈[0,n)a^ixi\hat F(x) = \sum _{i \in [0,n)} \hat a_i x^i。

对 F^\hat F 进行点值变换（∀i∈[0,n),ti=ωn−i\forall i \in [0,n),t_i = \omega _n ^{-i}），设点值序列为 ss。

则有

∀i∈[0,n),si=F^(ωn−i)=∑j∈[0,n)a^j(ωn−i)j=∑j∈[0,n)ωn−ija^j=∑j∈[0,n)ωn−ij∑k∈[0,n)akωnjk=∑j∈[0,n),k∈[0,n)ωn−ijakωnjk=∑j∈[0,n),k∈[0,n)ωnj(k−i)ak=∑k∈[0,n)ak∑j∈[0,n)ωnj(k−i)=∑k∈[0,n)ak∑j∈[0,n)(ωnk−i)j \begin{aligned} \forall i \in [0,n), s_i & = \hat F(\omega _n ^{-i}) \\ & = \sum _{j \in [0,n)} \hat a_j (\omega _n ^{-i}) ^j \\ & = \sum _{j \in [0,n)} \omega _n ^{-ij} \hat a_j \\ & = \sum _{j \in [0,n)} \omega _n ^{-ij} \sum _{k \in [0,n)} a_k \omega _n ^{jk} \\ & = \sum _{j \in [0,n), k \in [0,n)} \omega _n ^{-ij} a_k \omega _n ^{jk} \\ & = \sum _{j \in [0,n), k \in [0,n)} \omega _n ^{j(k-i)} a_k \\ & = \sum _{k \in [0,n)} a_k \sum _{j \in [0,n)} \omega _n ^{j(k-i)} \\ & = \sum _{k \in [0,n)} a_k \sum _{j \in [0,n)} (\omega _n ^{k-i}) ^j \\ \end{aligned}

显然第二个求和是一个等比数列，由等比数列求和公式 ∑i∈[m,n)pi=pm−pn1−p\sum _{i \in [m,n)} p^i = \frac {p^m - p^n} {1 - p} 得：

  • 当 ωnk−i≠1  ⟺  i≠k\omega _n ^{k-i} \not = 1 \iff i \not = k
∑j∈[0,n)(ωnk−i)j=1−ωn(k−i)n1−ωnk−i=1−(ωnk−i)n1−ωnk−i=1−11−ωnk−i=0 \begin{aligned} \sum _{j \in [0,n)} (\omega _n ^{k-i}) ^j & = \frac {1 - \omega _n ^{(k-i) n}} {1 - \omega _n ^{k-i}} \\ & = \frac {1 - (\omega _n ^{k-i}) ^n} {1 - \omega _n ^{k-i}} \\ & = \frac {1 - 1} {1 - \omega _n ^{k-i}} \\ & = 0 \end{aligned}
  • 当 ωnk−i=1  ⟺  i=k\omega _n ^{k-i} = 1 \iff i = k
∑j∈[0,n)(ωnk−i)j=∑j∈[0,n)1=n \sum _{j \in [0,n)} (\omega _n ^{k-i}) ^j = \sum _{j \in [0,n)} 1 = n

因此

∀i∈[0,n),si=∑k∈[0,n)ak∑j∈[0,n)(ωnk−i)j=nai \begin{aligned} \forall i \in [0,n), s_i & = \sum _{k \in [0,n)} a_k \sum _{j \in [0,n)} (\omega _n ^{k-i}) ^j \\ & = n a_i \\ \end{aligned}

于是我们有

∀i∈[0,n),ai=sin \forall i \in [0,n), a_i = \frac {s_i} n

构造单位根

  • FFT

在复数域下，有 ωn=cos⁡2πn+isin⁡2πn\omega _n = \cos \frac {2 \pi} n + \mathrm i \sin \frac {2 \pi} {n}。

其中 i=−1\mathrm i = \sqrt {-1} 是 虚数单位，可以用 C++ 中的 complex 库中的 std::complex<double/long double> 存储复数。

  • NTT

对于模数 P∈P,∃n,k∈Z+,P=2nk+1P \in \mathbb P, \exists n,k \in \mathbb Z^+, P=2^nk+1，在模 PP 意义下有 ωn≡gP−1n\omega _n \equiv g ^ {\frac {P-1} n}，其中 gg 是原根。

gg 是模 PP 意义下的原根当且仅当 gi≢1(modP),∀i∈[1,ϕ(P))g ^i \not \equiv 1 \pmod P,\forall i \in [1,\phi(P)) 且 gϕ(P)≡1(modP)g ^{\phi(P)} \equiv 1 \pmod P。

specially，∀P∈P\forall P \in \mathbb P，其原根 gg 满足 ∀i∈[1,P−1),gi≢1(modP)\forall i \in [1,P-1), g ^i \not \equiv 1 \pmod P 且 gP−1≡1(modP)g^{P-1} \equiv 1 \pmod P。

于是对 n=2m,m∈Z+n = 2 ^m, m \in \mathbb Z ^+，我们有 ωnn≡gP−1n⋅n≡gP−1≡1,(modP)\omega _n ^n \equiv g ^{\frac {P - 1} {n} \cdot n} \equiv g ^{P - 1} \equiv 1, \pmod P，且 ωnn2≡gP−12≡±gP−1≡±1(modP)\omega _n ^{\frac n 2} \equiv g ^{\frac {P - 1} 2} \equiv \pm \sqrt {g ^ {P - 1}} \equiv \pm 1 \pmod P，又 gP−12≢1(modP)g ^ {\frac {P-1} 2} \not \equiv 1 \pmod P，所以 ωnn2≡−1(modP)\omega _n ^{\frac n 2} \equiv -1 \pmod P。

还有 ω2n2k≡g2k(P−1)2n≡gk(P−1)n≡ωnk(modP)\omega _{2n} ^{2k} \equiv g ^{\frac {2k(P-1)} {2n}} \equiv g ^{\frac{k(P-1)} n} \equiv \omega _n ^k \pmod P

由于原根的特殊性，模数 P∈PP \in \mathbb P 有特殊的限制，一般有 P=k2m+1,k,m∈Z+P = k 2 ^m + 1, k,m\in \mathbb Z ^+。

常见的模数有

167772161=5×225+1,g=3469762049=7×226+1,g=3754974721=45×224+1,g=11998244353=119×223+1,g=31004535809=479×221+1,g=3 \begin{aligned} 167772161 = 5 \times 2 ^{25} + 1, g = 3 \\ 469762049 = 7 \times 2 ^{26} + 1, g = 3 \\ 754974721 = 45 \times 2 ^{24} + 1, g = 11 \\ 998244353 = 119 \times 2 ^{23} + 1, g = 3 \\ 1004535809 = 479 \times 2 ^{21} + 1, g = 3 \\ \end{aligned}