Steven_MengのBlog

这两个”根“在多项式乘法里面运用非常广泛。

单位根(FFT)

关于我自己对单位根的理解。

单位根其实就是一些复数,他们的模长为$1$。

所以单位根一定在单位圆上

假设一个单位根$z$的极角为$\theta$,那么我们可以将$z$表示为$\cos \theta +i \sin \theta$

数形结合考虑,从圆上某一个点做一条垂线,那么垂线长度为$\sin \theta$,垂足到原点距离为$\cos \theta$

考虑使用向量模长验证,$|z|=\sqrt{\sin ^2 \theta + \cos ^2 \theta}=1$

$\omega_n^k = \cos \dfrac{k}{n} 2 \pi+ i \sin \dfrac{k}{n} 2 \pi $

感性地理解这个式子,注意到$2 \pi$为$360°$,所以这个式子的意义就是将单位圆用一些经过圆心的线分成$n$份,从$1+0i$往逆时针数$k$次,数到的线的端点所代表的复数。

于是发现四个推$FFT$所用的经典的式子都非常$naive$

$1.\omega _n^k=\omega _{2n}^{2k}$

这个代表的意思就是把单位圆分成$n$份,数$k$次,和分成$2n$份,数$2k$次所代表复数是一样的。非常智障。

也可以通过三角函数证明:

$\omega^k_n=\cos{k\over n}2 \pi +i\sin{k\over n} 2\pi =\cos{2k\over 2n}2\pi+i\sin{2k\over 2n} 2\pi=\omega^{2k}_{2n}$

$2.\omega _n^{k+{n \over 2}}=-\omega _n^k$

定义:对于复数$z=a+bi$,$-z=-a-bi$

这个也非常好理解,$n/2$代表半圈,所以这个式子的意思是从编号为$k$的复数开始走半圈,代表的复数和之前的正好相反(实部和虚部都相反)

$3. \omega _n^0=\omega _n^n =1,\omega _n^{\dfrac{n}{2}}=-1$

编号为$0$和编号为$n$的点代表的复数相等,都为$1+0i$,编号为$n/2$的点其实就是$1+0i$转过半圈,就是$-1+0i$

$4.\omega _n^p \times \omega _n^q = \omega _n ^ {p+q}$

复数的乘法其实像三角函数一样,设$z_1=a_1+ib_1,z_2=a_2+ib_2$

根据复数乘法定义,那么我们有$z_1 \times z_2 = (a_1 \times a_2 - b_1 \times b_2)+i(a_1 \times b_2+a_2 \times b_1)$

我们有三角函数的合角公式:

$\sin(A+B)=\sin A \cos B+\cos A \sin B$
$\cos (A+B)=\cos A\cos B-\sin A \sin B$

换元:$\alpha = \f\dfrac}{n} 2 \pi, \beta = \f\dfrac}{n} 2 \pi $

于是$\omega _n^p = \cos \alpha + i \sin \alpha$

还有$\omega _n^q = \cos \beta + i \sin \beta$

于是$\omega _n ^p \times \omega _n ^q = (\cos \alpha \cos \beta-\sin \alpha \sin \beta) + i (\sin \alpha \cos \beta+\cos \alpha \sin \beta) = \cos (\alpha + \beta)+i \sin(\alpha +\beta) = \omega ^{p+q}_n$

(吐槽一句,复数的乘法好像就是为了这个东西定义的)

这个式子要好好体会。

有了第四个式子,我们就可以再推出第三个式子:

$\omega _n ^{k+\dfrac{n}{2}}=\omega _n^{\dfrac{n}{2}} \times \omega _n^k = (-1+0i) \times \omega _n^k = -\omega_n^k$

原根(NTT)

有时候题目要求对一个大质数取模,这时就不能用单位根,要用原根。

$p$的原根是满足$g^0\%p,g^1\%p,g^2\%p…g^{p-2}\%p$恰好等于$[1,p-1]$中的所有数的最小的$g$。

现实中,可以从$2 \to p-1$枚举$g$,如果满足$g ^\frac{p-\dfraci} !=1 \pmod p$均成立,那么我们就找到了$p$的原根。

我们称$g_n$为$n$的原根,那么我们也得到了类似于$\omega_n^k$一长串的$g_n^0,g_n^1,g_n^2, … ,g^{n-2}_{n}$,而且他们模意义下和$[1,p-1]$中的所有数一一对应。

我们设一个素数$p=a \times 2^b+1$

有以下等价关系:$g_n=g^{\fra\dfrac}{n}} \Leftrightarrow \omega_n=\cos \fra\dfraci}{n}+i\sin\fra\dfraci}{n}$。(下面证明)

并且有$g_n^k=g^{\f\dfrac-1}{n} \times k}$

显然有$g_n^p \times g_n^q=g^{\f\dfrac-1}{n} \times (p+q)}=g_n^{p+q}$。

$1.g_{2n}^{2k}=g_n^k$

显然,$g_{2n}^{2k}=g^{\f\dfrac-1}{2n} \times 2k}=g^{\f\dfrac-1}{n}k}=g_n^k$。

$2.g_n^{\dfrac{n}{2}}=-1,g_n^{0}=g_{n}^n=1$

显然$g_n^0=g^0=1,g_n^n=g^{p-1}=1 \pmod p$。

因为$(g_n^{\dfracn}{2}})^2=g_n^n=1$

得$g_n^{\dfracn}{2}}=\pm 1$。

又因为$g_n^n!=g_n^{\f\dfrac}{2}}$,且$g_n^n=1$,所以$g_n^{\frac\dfrac}}=-1$。

$3.g_n^{k+\dfrac{n}{2}}=-g_n^k$

上面的式子套入$p=k,q=\fra\dfrac2}$,显然。

 评论