从【高中数学】开始的 Fourier 变换-526互联

Intro

给定两个多项式 \(f,g\)，求出 \(f\cdot g\)。

\(\Theta(n^2)\) 的算法是 trivial 的。

那么如果 \(\deg f,g \leq 10^6\) 呢？

这就不得不用到 FFT（快速傅里叶变换）/NTT（快速数论变换）了。

Basis

Complex

我们都很熟悉复数的代数形式和三角形式。

代数形式：\(z=a+b\mathrm{i}\)。（\(a,b \in \mathbb{R}\)）
三角形式：\(z=r\left(\cos \theta+\mathrm{i}\sin \theta\right)\)

其中 \(\mathrm{i}\) 为虚数单位，满足 \(\mathrm{i}^2=-1\)。

我们定义复数 \(z=a+b\mathrm{i}\) 的共轭 \(\overline{z}=a-b\mathrm{i}\)，定义复数的模 \(|z|=\sqrt{z\overline{z}}=\sqrt{a^2+b^2}\)。

所有的复数 \(\left\{a+b\mathrm{i}:a,b\in \mathbb{R}\right\}\) 构成复数集，记为 \(\mathbb{C}\)。复数集是一个数域，这意味着，它对加减乘除封闭（除数当然不能为 \(0\)）。事实上，它对乘方开方操作也是封闭的。

例如，我们想计算 \(\sqrt{\mathrm{i}}\)，设 \(\sqrt{\mathrm{i}}=t\)，则 \(t^2=\mathrm{i}\)。

不妨设 \(t=a+b\mathrm{i}\)，其中 \(a,b\in \mathbb{R}\)，则 \(t^2=a^2-b^2+2ab\mathrm{i}\)，比对系数可得

\[\begin{cases} a^2-b^2=0,\\ 2ab=1 \end{cases} \]

于是不难解出 \(a\) 和 \(b\) 的取值。

复数 \(a+b\mathrm{i}\) 与复平面上的点 \((a,b)\) 一一对应，亦与复平面上的向量 \((a,b)'\) 一一对应。我们来回顾复数相加相乘的几何意义。

Addition

设

\[z_1=a_1+b_1\mathrm{i},z_2=a_2+b_2\mathrm{i} \]

且

\[\boldsymbol{z_1}=(a_1,b_1)',\boldsymbol{z_2}=(a_2,b_2)' \]

（本文以粗体+列向量的形式记向量）

则

\[z_3=z_1\pm z_2=\left(a_1\pm a_2\right)+\left(b_1\pm b_2\right)\mathrm{i} \]

\[\iff \boldsymbol{z_3}=\boldsymbol{z_1}\pm \boldsymbol{z_2} \]

即

复数相加减，其对应向量也相加减。

Multiplication

设

\[z_1=r_1(\cos \theta_1+\mathrm{i}\sin \theta_1), z_2=r_2(\cos \theta_2+\mathrm{i}\sin \theta_2)\]

\[\begin{aligned} z_3&=z_1\cdot z_2=r_1(\cos \theta_1+\mathrm{i}\sin \theta_1)\cdot r_2(\cos \theta_2+\mathrm{i}\sin \theta_2)\\ &=r_1r_2\left[\cos (\theta_1+\theta_2)+\mathrm{i}\sin (\theta_1+\theta_2)\right] \end{aligned} \]

\[\begin{aligned} z_3&=\frac{z_1}{z_2}=\frac{r_1(\cos \theta_1+\mathrm{i}\sin \theta_1)}{r_2(\cos \theta_2+\mathrm{i}\sin \theta_2)}\\ &=\frac{r_1}{r_2}\left[\cos (\theta_1-\theta_2)+\mathrm{i}\sin (\theta_1-\theta_2)\right] \end{aligned} \]

复数相乘，其对应向量的辐角相加，长度相乘。

复数相除，其对应向量的辐角相减，长度相除。

那么复数的乘方呢？

Power

对于 \(z\in \mathbb{C}\)，有

\[|z|^n=|z^n| \]

也就是说，模的平方等于平方的模。

我们有 De Moivre（棣莫弗）定理：

或者可以表述为

\[\left[r\left(\cos \theta+\mathrm{i}\sin \theta\right)\right]^n=r^n\left(\cos {n\theta}+\mathrm{i}\sin {n\theta}\right) \]

证明：考虑数学归纳法。显然只需证明 \(\left(\cos \theta+\mathrm{i}\sin \theta\right)^n=\cos {n\theta}+\mathrm{i}\sin {n\theta}\) 成立。

\(n=1\) 时，显然成立。

设 \(n=k\) 时 \(\left(\cos \theta+\mathrm{i}\sin \theta\right)^k=\cos {k\theta}+\mathrm{i}\sin {k\theta}\) 成立。

当 \(n=k+1\) 时，我们有

\( \begin{aligned} \text{右边}&=\cos \left[(k+1)\theta\right]+\mathrm{i}\sin \left[(k+1)\theta\right]\\ &=\cos k\theta\cos \theta -\sin k\theta \sin \theta +\mathrm{i}\sin k\theta \cos \theta+\mathrm{i}\cos k\theta \sin \theta\\ &=\cos \theta(\cos k\theta+\mathrm{i}\sin k\theta)+\mathrm{i}\sin \theta(\cos k\theta+\mathrm{i}\sin k\theta)\\ &=\left(\cos \theta+\mathrm{i} \sin\theta\right)\left(\cos k\theta+\mathrm{i} \sin k\theta\right)\\ &=\left(\cos \theta+\mathrm{i} \sin\theta\right)\left(\cos \theta+\mathrm{i} \sin \theta\right)^k \\ &=\left(\cos \theta+\mathrm{i} \sin\theta\right)^{k+1}=\text{左边} \end{aligned} \)

证毕。

考虑单位复数 \(z=\cos \theta+\mathrm{i}\sin \theta\)，即 \(\boldsymbol{z}=(\cos \theta,\sin \theta)'\)。

那么 \(z^2=\cos 2\theta+\mathrm{i} \sin 2\theta\)，其对应向量 \(\boldsymbol{z_2}=(\cos 2\theta,\sin 2\theta)'\)。

我们不难想到单位复数乘方的几何意义。

单位复数乘 \(\boldsymbol{n}\) 次方，就是将其自身的辐角变为 \(\boldsymbol{n}\) 倍。

那么我们考虑 单位根。

所谓 \(n\) 次单位根，就是指复数域内满足条件 \(\omega^{n}=1\) 的 \(\omega\)。