快速傅里叶变换，在竞赛中离散傅里叶变换DFT及其逆变换IDFT尤为常用，主要用于快速求多项式的乘积。形式化地说，多项式就是某个
f
(
x
)
=
∑
i
=
0
n
a
i
x
i
f(x)=\sum\limits^n_{i=0}a_ix^i
f(x)=i=0∑naixi，两个系数分别为
a
i
a_i
ai和
b
i
b_i
bi，那么
(
f
×
g
)
(
x
)
=
f
(
x
)
g
(
x
)
=
∑
i
=
0
n
∑
j
=
0
n
a
i
b
j
x
i
+
j
(f\times g)(x)=f(x)g(x)=\sum\limits^{n}_{i=0}\sum\limits_{j=0}^{n}a_ib_jx^{i+j}
(f×g)(x)=f(x)g(x)=i=0∑nj=0∑naibjxi+j，容易看出这个多项式是
2
n
2n
2n次的。
【补充知识1】我们接着先看一下一个叫卷积的东西。卷积实际上就是对应相乘，
(
f
⊗
g
)
(
x
)
=
∑
i
=
0
n
a
i
b
i
x
i
(f\otimes g)(x)=\sum\limits^{n}_{i=0}a_ib_ix^i
(f⊗g)(x)=i=0∑naibixi，可以稍微理解一下，实质上我们如果将乘法视为一种变换，卷积就是在向量上的变换的叠加。
【补充知识2】
其实，对于一条
n
n
n次的多项式曲线，我们可以通过类比认识到我们需要
n
+
1
n+1
n+1个不同的点就可以唯一确定这条曲线。比如说一次函数需两个点，二次函数需三个点，等等。我们考虑到，我们表达这些函数为
f
(
x
)
=
∑
i
=
0
n
a
i
x
i
f(x)=\sum\limits^n_{i=0}a_ix^i
f(x)=i=0∑naixi，那么如果我们现在得知了
n
+
1
n+1
n+1个函数上的点，直接代入就可以相应得出
n
+
1
n+1
n+1个方程，由于点两两不同，所以这个方程组一定恰有一组解，这也就确定了一条唯一的曲线。
好的，接下来是真正的内容。
我们可以发现，要确定最终的
(
f
⊗
g
)
(
x
)
(f\otimes g)(x)
(f⊗g)(x)，需要使用
2
n
+
1
2n+1
2n+1个点值表达，也就是在最终结果曲线上的
2
n
+
1
2n+1
2n+1个点。我们如果考虑在
f
(
x
)
f(x)
f(x)和
g
(
x
)
g(x)
g(x)上取
2
n
+
1
2n+1
2n+1个点，设为
(
x
i
,
y
f
i
)
(x_i,{y_f}_i)
(xi,yfi)和
(
x
i
,
y
g
i
)
(x_i,{y_g}_i)
(xi,ygi)，我们发现只要将其卷积一下，我们就能够找到这
2
n
+
1
2n+1
2n+1个点。这是很好理解的，因为将
y
f
i
{y_f}_i
yfi和
y
g
i
{y_g}_i
ygi卷积后作为新的纵坐标所得到的点，显然就在
(
f
⊗
g
)
(
x
)
(f\otimes g)(x)
(f⊗g)(x)上。
那么我们的问题就只剩下怎样计算和如何再次快速确定了。
我们考虑下分治，如果我们将系数向量中奇数项和偶数项分开来，我们会发现所得的两个式子间有一定的相似性：
a
1
x
1
+
a
3
x
3
+
⋯
+
a
2
k
+
1
x
2
k
+
1
a_1x^1+a_3x^3+\cdots+a_{2k+1}x^{2k+1}
a1x1+a3x3+⋯+a2k+1x2k+1
a
0
x
0
+
a
2
x
2
+
⋯
+
a
2
k
x
2
k
+
⋯
a_0x^0+a_2x^2+\cdots+a_{2k}x^{2k}+\cdots
a0x0+a2x2+⋯+a2kx2k+⋯
实际上，我们考虑将上面的式子变为
x
(
a
1
x
0
+
a
3
x
2
+
⋯
+
a
2
k
+
1
x
2
k
+
⋯
)
x(a_1x^0+a_3x^2+\cdots+a_{2k+1}x^{2k}+\cdots)
x(a1x0+a3x2+⋯+a2k+1x2k+⋯)，再将各项的次数折半（因为是偶数），我们现在就能够得到两个规模相对于原来的问题减半的子问题，可以递归求解，这里我们就得出了DFT的算法，由主定理对于
T
(
n
)
=
2
T
(
n
2
)
+
O
(
n
)
T(n)=2T(\frac{n}{2})+\text O(n)
T(n)=2T(2n)+O(n)，马上看出其复杂度
O
(
n
lg
n
)
\text O(n\lg n)
O(nlgn)。
但是，在还原的时候，我们却遇到了一个困难：我们如何将点值表达快速变为系数表达？难道我们去用高斯消元法？这样
O
(
n
3
)
\text O(n^3)
O(n3)岂不是比原来还慢？我们来观察一下DFT的实质。我们将DFT的效果写成这样一个矩阵：
[
1
x
0
⋯
x
0
n
1
x
1
⋯
x
1
n
⋮
⋮
⋱
⋮
1
x
n
⋯
x
n
n
]
\begin{bmatrix} 1 & x_0 & \cdots x_0^n \\ 1 & x_1 & \cdots x_1^n \\ \vdots & \vdots & \ddots & \vdots\\ 1& x_n & \cdots x_n^n\\ \end{bmatrix}
⎣⎢⎢⎢⎡11⋮1x0x1⋮xn⋯x0n⋯x1n⋱⋯xnn⋮⎦⎥⎥⎥⎤
稍微解释下，根据线性代数，这个东西乘上我们的系数向量之后所得就是对应的
x
=
x
0
,
1
,
⋯
,
n
x=x_{0,1,\cdots,n}
x=x0,1,⋯,n时
(
f
⊗
g
)
(
x
)
(f\otimes g)(x)
(f⊗g)(x)的结果。这个东西是很显然的，考虑用线性变换的角度理解。
然后我们考虑DFT的逆变换，即所谓IDFT，其的实质就是乘上DFT所乘上的这个矩阵的一个逆矩阵。由逆矩阵定义，我们可以考虑猜想在逆矩阵中
(
j
,
k
)
(j,k)
(j,k)处，数为
x
k
−
j
×
C
x_k^{-j}\times C
xk−j×C，其中
C
C
C是一个常数。那么如果将两个矩阵乘起来，再考虑
(
j
,
j
′
)
(j,j')
(j,j′)处的值，为
∑
k
=
0
n
x
k
j
′
−
j
C
\sum^{n}_{k=0}x_k^{j'-j}C
k=0∑nxkj′−jC要满足逆矩阵条件
V
V
−
1
=
I
n
VV^{-1}=I_n
VV−1=In，我们需要当且仅当
j
′
=
j
j'=j
j′=j的时候上式为
1
1
1，其余情况为
0
0
0。先看第一个条件，代进去得到
∑
k
=
0
n
C
=
1
\sum^n_{k=0}C=1
∑k=0nC=1，得
C
=
1
n
C=\frac{1}{n}
C=n1。代回去并根据第二个条件我们有
∑
k
=
0
n
x
k
j
′
−
j
=
0
(
j
′
≠
j
)
\sum^n_{k=0}x_k^{j'-j}=0(j'\neq j)
k=0∑nxkj′−j=0(j′=j)
然后我并不知道怎么一直推下去，于是我们直接来一个构造法。我们令
x
k
=
w
n
k
x_k=w_n^k
xk=wnk，然后我们就得到了一个等比数列，按照上式求和根据公式可以得到
∑
k
=
0
n
(
w
n
k
)
j
′
−
j
=
∑
k
=
0
n
(
w
n
j
′
−
j
)
k
=
(
w
n
j
′
−
j
)
n
−
1
w
n
j
′
−
j
−
1
=
0
\sum\limits_{k=0}^n(w_n^k)^{j'-j}=\sum\limits_{k=0}^n(w_n^{j'-j})^k=\frac{(w_n^{j'-j})^n-1}{w_n^{j'-j}-1}=0
k=0∑n(wnk)j′−j=k=0∑n(wnj′−j)k=wnj′−j−1(wnj′−j)n−1=0，即（这里跳了一步移项）
(
w
n
j
′
−
j
)
n
=
1
(w_n^{j'-j})^n=1
(wnj′−j)n=1我们又考虑到，
j
′
j'
j′和
j
j
j取遍
0
⋯
n
0\cdots n
0⋯n间的所有值，所以上式可以改为
(
w
n
k
)
n
=
w
n
k
n
=
1
(w^k_n)^n=w_n^{kn}=1
(wnk)n=wnkn=1，其中
k
k
k的值域为从
−
n
-n
−n到
n
n
n。
然后，我们考虑先取
k
=
1
k=1
k=1，本质上这里说的就是我们需要这样的一类不同的
2
n
2n
2n个数使得
(
w
n
)
n
=
1
(w_n)^n=1
(wn)n=1。显然在实数域中只能有
1
1
1（以及
−
1
-1
−1，因为我们在分治的时候预先补了零使得次数是
2
d
2^d
2d）满足这个性质，显然太少了，怎么办？
我们考虑扩展取值范围。一种方法，就是不只考虑实轴，我们可以考虑下复平面。也就是说，我们可以不只考虑
a
∈
R
a\in \mathbb{R}
a∈R，而是考虑所有
a
+
b
i
∈
C
a+bi\in \mathbb{C}
a+bi∈C，其中
a
,
b
∈
R
a,b\in \mathbb{R}
a,b∈R，而这里的
i
i
i，是一个曾经数学中往往避开的事物，满足
i
2
=
−
1
i^2=-1
i2=−1。实质上来说，复数可以理解为一种向量，比如说两个复数相加就是向量作用的叠加，而两个复数的积，则是另一种程度上的叠加。比方说我们考虑到，我们用极坐标也可以确定向量，进而确定复数，我们由变换
f
(
x
)
=
{
x
=
ρ
cos
θ
y
=
ρ
sin
θ
f(x)=\left\{ \begin{aligned} x & = &\rho \cos\theta \\ y & = & \rho\sin\theta \end{aligned} \right.
f(x)={xy==ρcosθρsinθ
我们可以得出在极坐标意义下
a
+
b
i
a+bi
a+bi可以写成
ρ
(
cos
θ
+
i
sin
θ
)
\rho(\cos\theta+i\sin\theta)
ρ(cosθ+isinθ)，考虑两个复数相乘的时候，我们有（涉及高中三角学知识，若无基础可以跳过）
ρ
1
(
cos
θ
1
+
i
sin
θ
1
)
×
ρ
2
(
cos
θ
2
+
i
sin
θ
2
)
=
ρ
1
ρ
2
(
cos
θ
1
c
o
s
θ
2
+
i
sin
θ
1
cos
θ
2
+
i
sin
θ
2
cos
θ
1
−
sin
θ
1
sin
θ
2
)
\rho_1(\cos\theta_1+i\sin\theta_1)\times \rho_2(\cos\theta_2+i\sin\theta_2)=\rho_1\rho_2(\cos\theta_1 cos\theta_2+i\sin\theta_1\cos\theta_2+i\sin\theta_2\cos\theta_1-\sin\theta_1\sin\theta_2)
ρ1(cosθ1+isinθ1)×ρ2(cosθ2+isinθ2)=ρ1ρ2(cosθ1cosθ2+isinθ1cosθ2+isinθ2cosθ1−sinθ1sinθ2)考虑利用各种和差化积公式（具体推导这里略去），得到乘积为
ρ
1
ρ
2
(
cos
(
θ
1
+
θ
2
)
+
i
sin
(
θ
1
+
θ
2
)
)
\rho_1\rho_2(\cos(\theta_1+\theta_2)+i\sin(\theta_1+\theta_2))
ρ1ρ2(cos(θ1+θ2)+isin(θ1+θ2))，实质上就是长度相乘，旋转角相加。
我在继续来考量下这个概念有什么用。上面的
(
w
n
)
n
=
1
(w_n)^n=1
(wn)n=1在变换群里面其实对应的是一种循环，称作生成元。我们考虑到，如果对应在复平面上，我们考虑令
ρ
=
1
\rho=1
ρ=1，然后长度上不管怎么乘都不会变，最后也就是
1
1
1（由于
ρ
\rho
ρ被要求是非负实数），然后神奇的东西来了，我们令
θ
=
2
π
/
n
\theta=2\pi/n
θ=2π/n，也就是将整个复平面划分成
n
n
n份，那么根据我们刚才的相乘原则，这个复数向量
cos
(
2
π
n
+
i
sin
(
2
π
n
)
)
\cos(\frac{2\pi}{n}+i\sin(\frac{2\pi}{n}))
cos(n2π+isin(n2π))实际上就是我们所要求的
w
n
w_n
wn。继续考量下它的性质，如果考虑
w
n
k
(
0
≤
k
<
n
)
w_n^k(0\leq k< n)
wnk(0≤k<n)，其的
n
n
n次方也是
1
1
1，因为
(
w
n
k
)
n
=
(
w
n
n
)
k
=
1
k
=
1
(w_n^k)^n=(w_n^n)^k=1^k=1
(wnk)n=(wnn)k=1k=1，同时在复数意义下，这
n
n
n个数也是两两不同的，所以我们如果代入这
n
n
n个数，我们就可以在
O
(
n
lg
n
)
\text O(n\lg n)
O(nlgn)的时间内计算出IDFT，而且代码上和DFT差不多，因为只是最后多除了个
n
n
n，同时把
w
n
k
w_n^k
wnk换成了
w
n
−
k
w_n^{-k}
wn−k，因此也可以写在一起，传入参数在某几步上加个特判。
同时复数还有性质
w
n
k
+
n
/
2
=
w
n
k
×
w
n
n
/
2
w_n^{k+n/2}=w_n^k\times w_n^{n/2}
wnk+n/2=wnk×wnn/2，而又容易由角度看出
w
n
n
/
2
=
−
1
w_n^{n/2}=-1
wnn/2=−1，所以
w
n
k
+
n
/
2
=
−
w
n
k
w_n^{k+n/2}=-w_n^k
wnk+n/2=−wnk。这个东西可以用来稍微改进下DFT，这样我们的计算量大概减少了一半左右，代码也是更容易写了。
不过，虽然说DFT在理论上是没有误差的，但是鉴于三角函数浮点数上计算有不小的误差，所以说如果多项式的系数向量都是整数的话，显然最后的系数向量也是整数，那么我们完全可以不在复数域下进行，而是在另一种同样具有群性质的数系下进行，比如说我们同样熟悉的模域下。而这就要在数论上进行讨论了，所以并不写，坑等以后再填……
好吧，最后再提一下，其实是有四种傅里叶变换的，分别对应着时域和频域上的离散和连续，其中如果两个域都是连续的，实质上就是傅里叶级数，也就是将一个函数展开成许多三角函数构成的无穷级数。再换句话说，就是用许多正（余）弦波的叠加去不断拟合某条给定的曲线。当然，你也可以用方波去拟合，这就涉及到快速沃尔什变换（FWT）了。
