看到各位神仙已经写的够详细了,我也来写写我的见解吧。

# 多项式

# 多项式是什么

关于多项式,我们已经在小学一年级的时候已经认识了,所以就不多说了。

# 多项式的表示方法

# 多项式的系数表示法

fif_i 表示 nn 次多项式F(x)F(x) ii 次项的系数,则

F(x)=i=0nfixiF(x)=\sum_{i=0}^nf_ix^i

# 点值表示法

我们在小学二年级的时候学过,一个 nn 次多项式 F(x)F(x) 可以由 n+1n+1 个不同的点 (xi,F(xi))(x_i,F(x_i)) 确定。如果不明白的话没关系,这不重要。

# 多项式的乘法

关于多项式的乘法,我们已经在小学二年级学过了。我也就不多说了。

很明显,系数表示法下朴素算法的时间复杂度是 Θ(nm)\Theta(nm),会被卡。

那点值表示法呢?看上去只要每个点和对应的点乘一乘就好了,复杂度 Θ(nm)\Theta(nm),但从系数表示法转换成点值表示法是 Θ(nm)\Theta(nm) 的。

怎么优化呢?这就用到我们的 FFT&NTT\text{FFT}\&\text{NTT}了。

# FFT

在学习 FFT 之前,我们先来复习一下我们小学三年级学的复数单位根

# 复数

# 复数的概念

我们把形如 z=a+biz=a+bia,ba,b 均为实数)的数称为复数,其中 aa 称为实部,bb 称为虚部ii 称为虚数单位。 ——百度百科

我觉得这已经讲得够详细了,我就不补充了。

# 复数的运算

  • 复数的加法:(a+bi)+(c+di)=(a+c)+(b+d)i(a+bi)+(c+di)=(a+c)+(b+d)i
  • 复数的减法:同理
  • 复数的乘法:(a+bi)(c+di)=ac+adi+bcibd=(acbd)+(ad+bc)i(a+bi)(c+di)=ac+adi+bci-bd=(ac-bd)+(ad+bc)i

此外,复数相乘在极坐标中的几何意义是:模长相乘,幅角相加

# 单位根

# 单位根的定义

数学上,nn 次单位根是 nn 次幂为 11 的复数。它们位于复平面的单位圆上,构成正 nn 边形的顶点,其中一个顶点是 11nn次单位根的模为 11 ——百度百科

nn 次单位根共有 nn 个,它们是:

cos2kπn+isin2kπn\cos\frac{2k\pi}{n}+i\sin\frac{2k\pi}{n}

其中 kk 是整数且 1kn1\leq k \leq n

配合图片理解(n=8n=8 的情况):

我们把 cos2πn+isin2πn\cos\frac{2\pi}{n}+i\sin\frac{2\pi}{n} 记为 ωn\omega_n(如图中的 DD表示的复数,我们就把它记作 ω8\omega_8)。

显然,ωnk=cos2kπn+isin2kπn\omega_n^k=\cos\frac{2k\pi}{n}+i\sin\frac{2k\pi}{n}

# 单位根的性质:

  1. ωn0=1\omega_n^0=1

显然。

  1. ωnn=1\omega_n^n=1

证明:ωnn=ωnk=cos2nπn+isin2nπn=cos2π+sin2π=1+0=1\omega_n^n=\omega_n^k=\cos\frac{2n\pi}{n}+i\sin\frac{2n\pi}{n}=\cos 2\pi+\sin 2\pi=1+0=1

  1. ω2n2k=ωnk\omega_{2n}^{2k}=\omega_n^k

证明:ω2n2k=cos4kπ2n+isin4kπ2n=cos2kπn+isin2kπn=ωnk\omega_{2n}^{2k}=\cos\frac{4k\pi}{2n}+i\sin\frac{4k\pi}{2n}=\cos\frac{2k\pi}{n}+i\sin\frac{2k\pi}{n}=\omega_n^k

  1. ωnn2=1\omega_{n}^{\frac{n}{2}}=-1

证明:ωnn2=cosnπn+isinnπn=cosπ+isinπ=1\omega_{n}^{\frac{n}{2}}=\cos\frac{n\pi}{n}+i\sin\frac{n\pi}{n}=\cos\pi+i\sin\pi=-1

# 快速傅里叶变换(FFT)

上面讲了一大堆什么单位根,有什么用呢?没错!我们要把它们带入多项式里去。

前面说过,一个 nn 次多项式 F(x)F(x) 可以由 n+1n+1 个不同的点 (xi,F(xi))(x_i,F(x_i)) 确定。我们这里令nnF(x)F(x) 的次数 +1+1

但显然,仅仅是简单的带入和朴素算法没区别。但利用单位根的性质,我们可以使用分治进行优化。

不妨把一个多项式 F(x)F(x) 按照奇偶性分成两组:

F(x)=f0x0+f1x1+f2x2+=(f0x0+f2x2+f4x4+)+(f1x1+f3x3+f5x5+)=(f0x0+f2x2+f4x4+)+x(f1x0+f3x2+f5x4+)\begin{aligned}F(x)&=f_0x^0+f_1x^1+f_2x^2+\dots\\&=(f_0x^0+f_2x^2+f_4x^4+\dots)+(f_1x^1+f_3x^3+f_5x^5+\dots)\\&=(f_0x^0+f_2x^2+f_4x^4+\dots)+x(f_1x^0+f_3x^2+f_5x^4+\dots)\end{aligned}

我们令 L(x)=f0x0+f2x1+f3x2+L(x)=f_0x^0+f_2x^1+f_3x^2+\dotsR(x)=f1x0+f3x1+f5x2+R(x)=f_1x^0+f_3x^1+f_5x^2+\dots

显然,F(x)=L(x2)+xR(x2)F(x)=L(x^2)+xR(x^2)

然后我们带入 ωnk\omega_n^k

,得到

F(ωnk)=L(ωn2k)+ωnkR(ωn2k)=L(ωn2k)+ωnkR(ωn2k)\begin{aligned}F(\omega_n^k)&=L(\omega_n^{2k})+\omega_n^kR(\omega_n^{2k})\\&=L(\omega_\frac{n}{2}^k)+\omega_n^kR(\omega_\frac{n}{2}^k)\end{aligned}

然后我们发现,L(x)L(x)R(x)R(x)xx 取值范围是 ωn20ωn2n21\omega_\frac{n}{2}^0\sim\omega_\frac{n}{2}^{\frac{n}{2}-1},但这里的 kk 取值范围是 0n10\sim n-1,明显超过了。但别忘了,ωnn2=1\omega_{n}^{\frac{n}{2}}=-1。我们把 ωnk+n2\omega_n^{k+\frac{n}{2}}带入。

F(ωnk+n2)=L(ωn2k+n)+ωnk+n2R(ωn2k+n)=L(ωn2k)ωnkR(ωn2k)\begin{aligned}F(\omega_n^{k+\frac{n}{2}})&=L(\omega_n^{2k+n})+\omega_n^{k+\frac{n}{2}}R(\omega_n^{2k+n})\\&=L(\omega_\frac{n}{2}^k)-\omega_n^kR(\omega_\frac{n}{2}^k)\end{aligned}

于是我们在计算 F(ωnk)F(\omega_n^k) 的时候同时计算 F(ωnk+n2)F(\omega_n^{k+\frac{n}{2}})

# 快速傅里叶逆变换

转换成点至表示法运算完之后还需要重新转换成系数表示法。

gi=F(ωni)g_i=F(\omega_n^i)G(x)=i=0ngixiG(x)=\sum_{i=0}^ng_ix^i

看似无从下手呢。

于是我们可以考虑上网搜题解。

网上的题解显示先带一个 ωnk\omega_n^{-k}然后直觉告诉我们这是对的。

G(ωnk)=i=0n1giωnki=i=0n1(j=0n1fjωnij)ωnki=i=0n1j=0n1fjωnijωnki=j=0n1fji=0n1ωn(jk)i\begin{aligned}G(\omega_n^{-k})&=\sum_{i=0}^{n-1}g_i\omega_n^{-ki}\\&=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}f_j\omega_n^{ij})\omega_n^{-ki}\\&=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}f_j\omega_n^{ij}\omega_n^{-ki}\\&=\sum_{j=0}^{n-1}f_j\sum_{i=0}^{n-1}\omega_n^{(j-k)i}\end{aligned}

我们先对 i=0n1ωn(jk)i\sum_{i=0}\limits^{n-1}\omega_n^{(j-k)i} 这个式子下手。

分两种情况讨论:

  1. j=kj=k 时,显然这个式子的结果是 nn
  1. jkj\neq k 时,我们就用到了我们的等比数列求和大法。先看这个等式:
i=0n1ωn(jk)i=i=0n1ωn(jk)i\sum_{i=0}^{n-1}\omega_n^{(j-k)i}=\sum_{i=0}^{n-1}\omega_n^{(j-k)i}

它显然成立。我们在这个等式两边同时乘上 ωnjk\omega_n^{j-k},得到:

ωnjki=0n1ωn(jk)i=i=0n1ωn(jk)(i+1)\omega_n^{j-k}\sum_{i=0}^{n-1}\omega_n^{(j-k)i}=\sum_{i=0}^{n-1}\omega_n^{(j-k)(i+1)}

两等式相减,得

(ωn1jk1)i=0n1ωn(jk)i=1ωnn(\omega_{n-1}^{j-k}-1)\sum_{i=0}^{n-1}\omega_n^{(j-k)i}=1-\omega_n^{n}

想想单位根的某个性质。

(ωn1jk1)i=0n1ωn(jk)i=0i=0n1ωn(jk)i=0\begin{aligned}&\ \ \ \ \ \ (\omega_{n-1}^{j-k}-1)\sum_{i=0}^{n-1}\omega_n^{(j-k)i}&=&0\\&\Rightarrow\sum_{i=0}^{n-1}\omega_n^{(j-k)i}&=&0\end{aligned}

回到原式。我们发现,当 j=kj=k 时,i=0n1ωn(jk)i=n\sum_{i=0}\limits^{n-1}\omega_n^{(j-k)i}=n,且这种情况只有一次出现,其余情况 i=0n1ωn(jk)i\sum_{i=0}\limits^{n-1}\omega_n^{(j-k)i} 均等于 00

所以,

G(ωnk)=j=0n1fji=0n1ωn(jk)i=nfkfk=G(ωnk)n\begin{aligned}&\ \ \ \ \ \ G(\omega_n^{-k})&=&\sum_{j=0}^{n-1}f_j\sum_{i=0}^{n-1}\omega_n^{(j-k)i}\\&&=&nf_k\\&\Rightarrow f_k&=&\frac{G(\omega_n^{-k})}{n}\end{aligned}

好了,FFT的理论部分就讲到这里。

# NTT

# 铭谢

  • 感谢@attack 神仙的题解。这篇题解和那篇题解的思路是基本一样的,所以会有很多相似的地方。
2020 02 21 Fri 11:29:36
2020 10 17 Sat 07:00:25