FFT主要用于快速求多项式的乘积。多项式的乘积就叫做卷积
对\(F\)和\(G\)来说，显然暴力算法的复杂度是\(O(nm)\)，而FFT的时间复杂度为\(O(nlogn)\)
多项式的性质：用任意\(n+1\)个横坐标不同的点，可以唯一确定一个\(n\)次多项式。这个性质叫做多项式的点表示法
证明：设这个多项式\(f=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0\)，那么我们代入\(n+1\)个点可以获得\(n+1\)个方程，这是\(n+1\)元一次方程，写出系数行列式就会发现是范德蒙德行列式，由于横坐标不同，所以行列式的值不为\(0\)，于是方程有唯一解
设\(H=FG\)，于是\(H\)为\(n+m\)次多项式，我们选取\(n+m+1\)个点代入\(F,G\)之后即可确定\(H\)。这就是点表示法的好处，时间复杂度从\(O(nm)\)降低到了\(O(n+m)\)
于是我们现在要解决的问题是如何快速将一个多项式的系数表示法（也就是我们通常写出来的多项式）与点表示法互相转换
下文的\(f(x)=a_{n-1}x^{n-1}+...+a_1x+a_0\)
系数表示法转点表示法：我们要在取\(n+1\)个特殊点上下功夫，我们取复数域上的单位根
假设\(n\)是偶数，画出复数域上的单位圆：
设\(w_n^k\)表示将单位圆等分成\(n\)份，将\(x\)轴逆时针旋转\(\frac{2πk}{n}\)所得到的复数，其中\(k\)的取值为\([0,n-1]\)。比如上图，\(w_n^0=1\)，\(w_n^3=-i\)
\(w_n^k\)具有如下的性质：
1.\(\forall i\neq j,w_n^i\neq w_n^j\)
2.\(w_n^k=\cos(\frac{2kπ}{n})+i\sin(\frac{2kπ}{n})\)
3.\(w_{2n}^{2k}=w_n^k\)
4.\(w_n^{k+\frac{n}{2}}=-w_n^k\)
现在，我们将\(f\)奇数项和偶数项分开，有\(f=g+h\)，其中\(g(x)=a_{n-2}x^{n-2}+a_{n-4}x^{n-4}+...+a_2x^2+a_0,h=a _ {n-1} x ^ {n-1} + a _ {n-3}x^{n-3}+...+a_1x\)
将\(g\)中每个\(x\)用\(x^2\)代替可设\(φ_1(x)=a_{n-2}x^{\frac{n}{2}-1}+a_{n-4}x^{\frac{n}{2}-2}+...+a_2x+a_0\)，将\(h\)提取一个\(x\)并将剩下的式子的\(x\)用\(x^2\)代替可得\(φ_2(x)=a_{n-1}x^{\frac{n}{2}-1}+a_{n-3}x^{\frac{n}{2}-2}+...+a_1\)，于是\(f(x)=φ_1(x^2)+xφ_2(x^2)\)
现在，设\(k∈[0,\frac{n}{2}-1]\)，则\(f(w_n^k)=φ_1(w_n^{2k})+w_n^kφ_2(w_n^{2k})=φ_1(w_{\frac{n}{2}}^{k})+w_n^kφ_2(w_{\frac{n}{2}}^{k}),f(w_n^{k+\frac{n}{2}})=φ_1(w_n^{2k})-w_n^kφ_2(w_n^{2k})=φ_1(w_{\frac{n}{2}}^{k})-w_n^kφ_2(w_{\frac{n}{2}}^{k})\)
也就是说我们要求出将\(w_n^0,w_n^1,...,w_n^{n-1}\)代入\(f\)的值，只需要递归求解\(φ_1,φ_2\)即可；一共会划分\(O(\log n)\)层，每层的总复杂度为\(O(n)\)，所以时间复杂度为\(O(n\log n)\)（如果某一次\(n\)为奇数，我们最开始提出一个\(x\)即可）
点表示法转换为系数表示法：设我们现在已经知道了\((w_n^0,f(w_n^0)),...,(w_n^{n-1},f(w_n^{n-1}))\)，我们要求\(f(x)\)，则有\(a_k=\frac{\sum_{i=0}^{n-1}f(w_n^{i})(w_n^{-k})^i}{n}\)
证明：
\[\sum_{i=0}^{n-1}f(w_n^{i})(w_n^{-k})^i\\=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j(w_n^{i})^j)(w_n^{-k})^i\\=\sum_{i=0}^{n-1}(\sum_{j=0}^{n-1}a_j(w_n^{j})^i)(w_n^{-k})^i\\=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}a_j(w_n^{j-k})^i\\=\sum_{j=0}^{n-1}a_j\sum_{i=0}^{n-1}(w_n^{j-k})^i\\=na_k \]，最后一步成立是因为
\[\sum_{i=0}^{n-1}(w_n^{j-k})^i=\begin{cases} n,j=k \\ \frac{1-(w_n^{j-k})^n}{1-w_n^{j-k}}=\frac{1-(w_n^n)^{j-k}}{1-w_n^{j-k}}=\frac{1-1}{1-w_n^{j-k}}=0,j\neq k \end{cases} \]于是我们设\(\rho(x)=\sum_{i=0}^{n-1}f(w_n^{i})x^{i}\)，则我们求出\(\rho(w_n^{0}),\rho(w_n^{-1}),...,\rho(w_n^{-(n-1)})\)即可，这就是上文讲的傅里叶正变换（系数表示法转化为点表示法）
最后讲一下实现。实践证明，如果用递归来实现的话，常数是非常大的，所以我们一般利用迭代来实现
视频看到了2:08:00
标签：+...+,frac,多项式,sum,表示法,乘法,2k From： https://www.cnblogs.com/dingxingdi/p/18344567