FFT

一、简介

FFT（Fast Fourier Transformation），即快速傅里叶离散变换，作用为 $O(n\log n)$ 计算多项式乘法。

$F(x)$ 表示一个多项式，叫做“多项式 $F$ ”。

$F[n]$ 表示 $F(x)$ 的 $n$ 次项系数， $F(x)=\sum_{i=0}^{n}F[i]x^i$ 。

多项式有两种表达方式：一种是系数表示法；另一种是点值表示法。因为用系数表示法计算是 $O(n^2)$ 的（也就是高精度乘法的原理），因此我们考虑用点值表示法。

首先有个定理：用 $n+1$ 个点值可以确定一个 $n$ 阶的多项式。显然 $2$ 个点确定一次函数， $3$ 个点确定二次函数，因此类推。

用点值表示法表示多项式

F_1(x)={(x_0, F_1[x_0]),(x_1,F_1[x_1]),\ldots,(x_n,F_1[x_n])}

F_2(x)={(x_0, F_2[x_0]),(x_1,F_2[x_1]),\ldots,(x_n,F_2[x_n])}

那么多项式乘法即为

F_1(x)\times F_2(x)={(x_0, F_1[x_0]\times F_2[x_0]),(x_1,F_1[x_1]\times F_2[x_1]),\ldots,(x_n,F_1[x_n]\times F_2[x_n])}

只需要枚举每一阶然后相乘即可，时间复杂度为 $O(n)$ 。

因此有了 FFT 的基本流程：

首先有虚数单位 $i$ ，满足 $i^2=-1$ ，任何一个负数可以表示为 $a+bi$ ， $a$ 称为复数的实部， $b$ 称为复数的虚部。

任何实数可以在横轴上表示出来，而复数不行。现在加入一条数轴，这样就变成了一个坐标系，横轴称为实轴，竖轴称为虚轴，现在每个复数都可以用坐标系上的点表示。如形如 $a+bi$ 的复数可以表示为一个点 $(a,b)$ 。

复数相加：实部和虚部分别相加。
$(a+bi) + (c+di) = (a + c) + (b + d)i$
复数相减：取相反数再相加。
复数相乘：如多项式相乘。
$i^2=-1$ $(a+bi)\times (c+di)=a\times (c+di)\times bi\times (c+di)=ac+adi+bci+bdi^2=ac−bd+(ad+bc)i$
复数的共轭：两个复数实部相同，虚部相反。

一个复数和自己的共轭相乘一定会得到实数： $(a+bi)(a-bi)=a^2+b^2$ 。
复数相除：分子分母同城分母的共轭。
$\frac{a+bi}{c+di}=\frac{ac+bd}{c^2+d^2} + \frac{bc-ad}{c^2+d^2}$

复数相乘的几何意义非常重要：模长相乘，幅角相加。

模长：复数表示的点到原点的距离， $x=a+bi$ 的模长称为 $|x|$

幅角：原点到该点的射线与实轴正方向射线组成的角（逆时针旋转）的角度称作这个复数的幅角， $a+bi$ 的幅角称作 $arg(a+bi)$ 。