题解：P1919 【模板】高精度乘法 | A*B Problem 升级版

Sunrise_beforeglow · 2025-05-28 13:39:11 · 题解

了解 FFT

由于本人是 xxs，数学学的不多，还请多多谅解。

前情提要

我们都知道，高中数学有一个叫做复数的东西。

虚数单位 i 其实就是用来表示 x^2=-1 的根。

为什么一定要弄一个这个东西呢，因为我们知道平方具有非负性，但虚数不一样，i^2=-1，也就是 i=\sqrt{-1}。

那么复数，其实就是 a+bi 的形式，其中 a,b\in \mathbb{R}。

然后这个东西的加减乘除并不复杂，它也满足结合律，所以可以直接使用乘法、加法结合律计算，比如 (a+bi)(c+di)=ac+i^2bd+i(ad+bc)=ac-bd+i(ad+bc)。

这个复数在编程中可以手写，也可以使用 STL 中的 complex 项。

这里我放上自己手写的：

struct node
{
    double x,y;
    node operator +(const node &g)const{return {g.x+x,g.y+y};}
    node operator -(const node &g)const{return {x-g.x,y-g.y};}
    node operator *(const node &g)const{return {g.x*x-g.y*y,g.x*y+g.y*x};}
};

那么我们其实可以将它一一映射到平面直角坐标系上，其中 a+bi 在坐标系上可以唯一表示为点 (a,b)。

我们再在坐标系上画出一个单位圆，它的方程为 (x-0)^2+(y-0)^2=1，意思是所有 (x,y) 满足与 (0,0) 距离为 1 的点。

那么了解 FFT 之前，我们需要知道 n 次单位根，我们定义 \omega_n^1 为方程 x^n=1 的根。

那么所有的根分别为 \omega_n^0,\omega_n^1\cdots \omega_{n}^{n-1}。

这几个数的复数表示分别为 1,\cos(\dfrac{2\pi}{n})+i\sin(\dfrac{2\pi}{n})\cdots \cos((n-1)\dfrac{2\pi}{n})+i\sin((n-1)\dfrac{2\pi}{n})，也就是把单位圆平均分成 n 份。

大概的示意图就是这样：

我知道你们有很多疑问，让我们一个个解决。

为了方便，令 \alpha=\dfrac{2\pi}{n}。

首先我们需要知道单位圆的参数方程：

这个很好证，把这个带入单位圆的方程即可，意思是从 x 轴开始，在单位圆上逆时针转 \alpha 度。

所以这 n 个根都在单位圆上。

接下来，我们需要知道，当我们已经定义 w_n^1=\cos\alpha +i\sin \alpha 时，为什么 w_n^x=\cos x\alpha+i\sin x\alpha。

我们可以使用归纳法证明：

• 当 x=1 时，显然成立。

• 假设 x=k-1 时成立，那么 x=k 时。

所以，(w_n^i)^n=w_n^{ni}=\cos2\pi i+i\sin2\pi i=1。

于是 w_n^0,w_n^1\cdots w_n^{n-1} 为方程 x^n=1 的 n 个复数根。

于是，从几何意义上看，我们知道了 \omega_{2n}^k=-\omega_{2n}^{k+n}。

我们还要了解多项式。

什么是多项式，我们定义一个 n 次多项式 f(x)=a_{n-1}x^{n-1}\cdots a_0x_0=\sum\limits_{i=0}^{n-1}a_ix^i。

那么求 f(x) 的值，就是把 x 代入这个多项式。

我们也可以使用 (x_0,y_0)\cdots (x_{n-1},y_{n-1}) 这 n 个点来唯一确定这个多项式，毕竟这 n 个方程可以唯一确定这 n 个系数。

正片开始

FFT，其实就是把系数表示法转换为点值表示法，再转换为系数表示法，进而加速多项式运算的过程。

FFT 正变换

我们可以做如下变换：

然后我们令 F(x)=\sum\limits_{i=0}^{\frac{n}{2}-1}a_{2i}x^{2i},G(x)=\sum\limits_{i=0}^{\frac{n}{2}-1}a_{2i}x^{2i} 不难发现它们均为偶函数。

所以 f(\omega_n^k)=F(\omega_n^k)+\omega_n^kG(\omega_n^k)。