看到各位神仙已经写的够详细了,我也来写写我的见解吧。
多项式
多项式是什么
关于多项式,我们已经在小学一年级的时候已经认识了,所以就不多说了。
多项式的表示方法
多项式的系数表示法
设 fi 表示 n 次多项式F(x) i 次项的系数,则
F(x)=∑i=0nfixi 点值表示法
我们在小学二年级的时候学过,一个 n 次多项式 F(x) 可以由 n+1 个不同的点 (xi,F(xi)) 确定。如果不明白的话没关系,这不重要。
多项式的乘法
关于多项式的乘法,我们已经在小学二年级学过了。我也就不多说了。
很明显,系数表示法下朴素算法的时间复杂度是 Θ(nm),会被卡。
那点值表示法呢?看上去只要每个点和对应的点乘一乘就好了,复杂度 Θ(nm),但从系数表示法转换成点值表示法是 Θ(nm) 的。
怎么优化呢?这就用到我们的 FFT&NTT了。
FFT
在学习 FFT 之前,我们先来复习一下我们小学三年级学的复数和单位根
复数
复数的概念
我们把形如 z=a+bi(a,b 均为实数)的数称为复数
,其中 a 称为实部,b 称为虚部
,i 称为虚数单位
。 ——百度百科
我觉得这已经讲得够详细了,我就不补充了。
复数的运算
- 复数的加法:(a+bi)+(c+di)=(a+c)+(b+d)i
- 复数的乘法:(a+bi)(c+di)=ac+adi+bci−bd=(ac−bd)+(ad+bc)i
此外,复数相乘在极坐标中的几何意义是:模长相乘,幅角相加。
单位根
单位根的定义
数学上,n 次单位根是 n 次幂为 1 的复数。它们位于复平面的单位圆上,构成正 n 边形的顶点,其中一个顶点是 1。n次单位根的模为 1 ——百度百科
n 次单位根共有 n 个,它们是:
cosn2kπ+isinn2kπ其中 k 是整数且 1≤k≤n。
配合图片理解(n=8 的情况):

我们把 cosn2π+isinn2π 记为 ωn(如图中的 D表示的复数,我们就把它记作 ω8)。
显然,ωnk=cosn2kπ+isinn2kπ
单位根的性质:
- ωn0=1
显然。
- ωnn=1
证明:ωnn=ωnk=cosn2nπ+isinn2nπ=cos2π+sin2π=1+0=1
- ω2n2k=ωnk
证明:ω2n2k=cos2n4kπ+isin2n4kπ=cosn2kπ+isinn2kπ=ωnk
- ωn2n=−1
证明:ωn2n=cosnnπ+isinnnπ=cosπ+isinπ=−1
快速傅里叶变换(FFT)
上面讲了一大堆什么单位根,有什么用呢?没错!我们要把它们带入多项式里去。
前面说过,一个 n 次多项式 F(x) 可以由 n+1 个不同的点 (xi,F(xi)) 确定。我们这里令n为 F(x) 的次数 +1。
但显然,仅仅是简单的带入和朴素算法没区别。但利用单位根的性质,我们可以使用分治进行优化。
不妨把一个多项式 F(x) 按照奇偶性分成两组:
F(x)=f0x0+f1x1+f2x2+…=(f0x0+f2x2+f4x4+…)+(f1x1+f3x3+f5x5+…)=(f0x0+f2x2+f4x4+…)+x(f1x0+f3x2+f5x4+…)我们令 L(x)=f0x0+f2x1+f3x2+…,R(x)=f1x0+f3x1+f5x2+…
显然,F(x)=L(x2)+xR(x2)。
然后我们带入 ωnk。
,得到
F(ωnk)=L(ωn2k)+ωnkR(ωn2k)=L(ω2nk)+ωnkR(ω2nk)然后我们发现,L(x) 和 R(x) 的 x 取值范围是 ω2n0∼ω2n2n−1,但这里的 k 取值范围是 0∼n−1,明显超过了。但别忘了,ωn2n=−1。我们把 ωnk+2n带入。
F(ωnk+2n)=L(ωn2k+n)+ωnk+2nR(ωn2k+n)=L(ω2nk)−ωnkR(ω2nk)于是我们在计算 F(ωnk) 的时候同时计算 F(ωnk+2n)。
快速傅里叶逆变换
转换成点至表示法运算完之后还需要重新转换成系数表示法。
设 gi=F(ωni),G(x)=∑i=0ngixi
看似无从下手呢。
于是我们可以考虑上网搜题解。
网上的题解显示先带一个 ωn−k 。然后直觉告诉我们这是对的。
G(ωn−k)=i=0∑n−1giωn−ki=i=0∑n−1(j=0∑n−1fjωnij)ωn−ki=i=0∑n−1j=0∑n−1fjωnijωn−ki=j=0∑n−1fji=0∑n−1ωn(j−k)i我们先对 i=0∑n−1ωn(j−k)i 这个式子下手。
分两种情况讨论:
- 当 j=k 时,显然这个式子的结果是 n。
- 当 j=k 时,我们就用到了我们的等比数列求和大法。先看这个等式:
∑i=0n−1ωn(j−k)i=∑i=0n−1ωn(j−k)i它显然成立。我们在这个等式两边同时乘上 ωnj−k,得到:
ωnj−k∑i=0n−1ωn(j−k)i=∑i=0n−1ωn(j−k)(i+1)两等式相减,得
(ωn−1j−k−1)∑i=0n−1ωn(j−k)i=1−ωnn想想单位根的某个性质。
(ωn−1j−k−1)i=0∑n−1ωn(j−k)i⇒i=0∑n−1ωn(j−k)i==00回到原式。我们发现,当 j=k 时,i=0∑n−1ωn(j−k)i=n,且这种情况只有一次出现,其余情况 i=0∑n−1ωn(j−k)i 均等于 0。
所以,
G(ωn−k)⇒fk===j=0∑n−1fji=0∑n−1ωn(j−k)infknG(ωn−k)
好了,FFT的理论部分就讲到这里。
NTT
铭谢
- 感谢@attack 神仙的题解。这篇题解和那篇题解的思路是基本一样的,所以会有很多相似的地方。