快速傅里叶变换FFT简明教程

给出长度为$n$的多项式$f(x)={\sum }_{i=0}^{n?1}{a}_i{x}^i$和长度为$m$多项式$g(x)={\sum }_{i=0}^{m-1}{b}_i{x}^i$。求解多项式$h(x)=f(x)\times g(x)$。
$(1\le n\le 10^5)$

多项式的两种表示方法，系数表示法和点值表示法。
系数表示法：我们存储$f(x)$的每一项$x^i$的系数$a_i$。
点值表示法：由大家都知道知，$N$个点可以确定一个最高次为$N-1$多项式，所以我们可以存储多项式上任意$N$个点，来确定这个多项式。

点值表示法有个性质是，对于多项式$f$的一个点值$(x,y_1)$，和多项式$g$的一个点值$(x,y_2)$，可以得到两个多项式相乘的多项式$h$在横坐标为$x$处的点为$(x,y_1\times y_2)$。

所以在对于长度为$n$的多项式$f$和长度为$m$的多项式$g$做乘法时，我们可以算出$f$的$n+m-1$个点值和$g$的$n+m-1$个点值，且要求两个多项式点值所取的$x$相同。
我们就可以通过遍历算出这$n+m-1$个横坐标的点值纵坐标相乘，来得到相乘后多项式的$n+m-1$个点值，也就是新多项式的点值表示法。
(注意：虽然我们存储$f$只需要$n$个点值，但是为了计算出长度为$n+m-1$的$h$，我们仍要先得到$f$的(n+m-1)个点值)

因此，假如我们可以通过$o(nlogn)$的办法，将系数表示法转化为点值表示法，然后将两个多项式点值$o(n)$相乘，最后通过$o(nlogn)$的办法将点值表示法转化回系数表示法，就可以解决这个问题了。

后面来介绍如何将系数表示发和点值表示法进行转换。

对于没有周期的函数，我们可以认为其周期为$\infty$，用无穷个周期函数去拟合。
同理，对于一个长度为$N$的离散多项式$x(n)(n=0,1,2..N-1)$，可以通过$N$个周期函数来拟合。（$N$个周期函数只能拟合$N$个点，不能用来拟合连续多项式函数）
由此我们得到离散傅里叶级数展开式如下。
$$X(k)=\sum _{n=0}^{N-1}x(n)e^{-2\pi ik\frac{n}{N}}$$
其中$e^{-2\pi ik\frac{n}{N}}=cos(-2\pi k\frac{n}{N})+isin(-2\pi k\frac{n}{N})$是关于$n$的周期为$N$的函数。（由欧拉公式$e^{ix}=cosx+isinx$得）

对于变换后得到的$X(n)$，我们可以通过离散傅里叶逆变换公式得到原函数$x(n)$。与$DFT$公式差不多，在原来的基础上$i$变成了$-i$，前面乘上一个$\frac{1}{N}$。公式如下。
$$x(n)=\frac{1}{N}\sum _{k=0}^{N-1}X(k)e^{2\pi ik\frac{n}{N}}$$

由前面讲过的，我们要解决的核心问题就是，算出多项式的$N$个点值。
大致做法是，我们求出函数在离散傅里叶变换后的N个点值，由点值乘出新多项式后，再将其逆变换回系数表示法。

我们先来观察式子$DFT$的式子。
我们为了简化式子，我们把$e^{\frac{2\pi ik}{N}}$用$W_N$代替。($W_N$是一个关于$k$的函数)
得到式子如下。
$$X(k)=\sum _{n=0}^{N-1}x(n)W_N^n(k)$$
然后观察$W_N$如下。
W N ( k ) = e 2 π i N = c o s ( 2 π k N ) + i s i n ( 2 π k N ) W_{N}(k)=e^{\frac{2\pi i}{N}}=cos(\frac{2\pi k}{N})+isin(\frac{2\pi k}{N}) WN​(k)=eN2πi​=cos(N