FFT即快速傅里叶变换，离散傅里叶变换及其逆变换的快速算法。在OI中用来优化多项式乘法。
FFT涉及到的概念
多项式
可表示为$A(x)$。设$A(x)$为$n$次，那么有$A(x)=a_0+a_1x+a_2x^2+...+a_nx^n$
系数表示法：
即用$n+1$个系数来表示一个$n$次多项式，即$(a_0,a_1,...,a_n)$。
我们可以将$(a_0,a_1,...,a_n)$看做一个系数向量。
点值表示法：
当自变量$x$分别取$n+1$个不同的值时，会得到$n+1$个对应的结果。可以将多项式看做一个$n$次函数，这个函数被$n+1$个点$(x_0,y_0),(x_1,y_1),...,(x_n,y_n)$确定。因此我们可以用点值表达式$(A(x_0),A(x_1),...,A(x_n))$来表示多项式$A(x)$
我们可以将$(A(x_0),A(x_1),...,A(x_n))$看做一个点值向量，也就等同于$(y_0,y_1,...,y_n)$
复数
形如$a+bi$，可以理解为复平面上的向量$(a,b)$
复数的乘法法则几何意义上可以理解为模长相乘，幅角相加。代数意义上可以理解为$(a+bi)(c+di)=ac-bd+(ad+bc)i$
单位根
在复平面内以原点为圆心，1为半径作圆。称这个圆为单位圆。
以$(1,0)$为起点，将圆$n$等分。设点$(1,0)$为第0个，那么这些等分点称为$n$次单位根。记作$\omega_n^k$。由于模长均为1，所以根据复数乘法法则，这$n$个等分点可以依次表示为$\omega_n^0$，$\omega_n$，$\omega_n^2$，...，$\omega_n^{n-1}$
根据三角函数，很容易推得单位根的表示方法：$\omega_n^k=cos\dfrac{2k\pi}{n}+isin\dfrac{2k\pi}{n}$ （欧拉公式）
性质一：$\omega_{2n}^{2k}=\omega_n^k$ （表示的是同一个点）
性质二：$\omega_n^k=-\omega_n^{k+\frac{n}{2}}$ （关于原点中心对称）
以上是FFT的前置知识。接下来开始介绍FFT。
多项式乘法
对于系数表达法的多项式乘法也就是初一课本里教的“逐项相乘”。复杂度$O(n^2)$
那么点值表达法的多项式乘法是如何的？考虑有两个多项式$A(x)$和$B(x)$。设$A(x) * B(x)=C(x)$。由于其点值向量已知，也就是说当$x$取$x_0$时，$A(x_0)$和$B(x_0)$是已知的，那么$C(x_0)=A(x_0)*B(x_0)$。
因此我们得到结论：两个点值表示的多项式相乘，只需要两个点值向量对应的项相乘即可。也就是说点值表达式的乘法复杂度为$O(n)$
离散傅里叶变换(DFT)及其逆变换(IDFT)
对于一个多项式$A(x)$，我们将它的点值向量$(A(\omega_n^0),A(\omega_n^1),...,A(\omega_n^{n-1}))$称为它的离散傅里叶变换。
相反的，我们将一个多项式的点值向量所对应的系数向量称为它的离散傅里叶逆变换。
注意，DFT中代入的各个值为单位根。
原文：https://www.cnblogs.com/qixingzhi/p/10052162.html