埋了一天的算导就当我看懂了？
。。。
目前仅限于学到FFT计算多项式系数向量的卷积，什么频域什么东西的那些我都不懂。。。。
我就大概讲一下？
首先我们对多项式的系数表达一般是这样的：
$$\sum_{i=0}^{n-1} a_i x^i$$
那么这个多项式的次数界为n，最高次数为n-1。
然后多项式的加减法很简单，是$O(n)$可以计算的，而乘法不一样，因为对于多项式$A(x)\times B(x)=C(x)$有
$$C(x)=\sum_{i=0}^{n-1} c_i x^i$$
其中
$$c_i=\sum_{k=0}^i a_kb_{i-k}$$
显然$O(n^2)$
我们将这种系数表示法的系数用一个a向量表示$a=(a_0, a_1, \cdots , a_{n-1})$，那么我们算多项式乘法实际上只要算多项式系数就行了。
定义卷积：
$$c = a \otimes b$$
a、b、c均为向量，而
$$c_i=\sum_{k=0}^i a_kb_{i-k}$$
其实就是这个定义卷积的定义。
接下来介绍一种很强大的表示方式，点值表示法。
首先一个次数界为n的多项式，一定能用n个点来表示出来（可以说是二维平面上的n个不同横坐标的点），多项式A的点值表达式即
$$\{(x_0, y_0), (x_1, y_1), \cdots , (x_{n-1}, y_{n-1})\}$$
其中$x_i$各不相同，且$y_k=A(x_k)$。而点值上多项式的加减法乘法都是O(n)的！（我都还没证。。先用着吧。。）
对于两个多项式$A$和$B$，运算后的多项式为$C$：
$$A=\{(x_0, y_{A, 0}), (x_1, y_{A, 1}), \cdots , (x_{n-1}, y_{A, n-1})\}$$
$$B=\{(x_0, y_{B, 0}), (x_1, y_{B, 1}), \cdots , (x_{n-1}, y_{B, n-1})\}$$
（注意$x_i$均对应相等！）
那么$C$的点值表示为：
$$C=A+B=\{(x_0, y_{A, 0}+y_{B, 0}), (x_1, y_{A, 1}+y_{B, 1}), \cdots , (x_{n-1}, y_{A, n-1}+y_{B, n-1})\}$$
$$C=A-B=\{(x_0, y_{A, 0}-y_{B, 0}), (x_1, y_{A, 1}-y_{B, 1}), \cdots , (x_{n-1}, y_{A, n-1}-y_{B, n-1})\}$$
$$C=A \times B=\{(x_0, y_{A, 0}y_{B, 0}), (x_1, y_{A, 1}y_{B, 1}), \cdots , (x_{n-1}, y_{A, n-1}y_{B, n-1})\}$$
！！！都是$O(n)$的！！
但是我们发现其实乘法是有缺陷的，就是a次界的多项式乘b次界的多项式得到的多项式的次数界应该是a+b-1的。
但是我们不怕！我们可以扩充！我们将向量$A$和$B$的次数界扩充到a+b-1！系数用0补齐！而点值表示法则多加几个点！
那么就行了。。。。
那么问题成功转化为如何将系数表示法转换到点值表示法，然后用O(n)解决它，然后再转换回系数表示法。其中系数表示法转换到点值表示法的操作叫求值运算，而点值转换到系数的操作叫做插值运算。他们是有良定义的互逆运算！
而有一种方法称作离散傅里叶变换（DFT）的东西可以实现两种操作，伟大的科学家发明了一种高效实现DFT的算法FFT，总复杂度为$O(nlogn)$。无限仰膜orz
然后再介绍点复数吧。。最让我感到神奇的是复数这个概念，，，好强大。。
复数的话我大概懂得这点？
复数有实部和虚部，其中虚部的单位是$i=$，定义为$e=a+bi$，带$i$的是虚部
然后当虚部为0时，这个复数就是实数。。。（也就是说实数是复数的子集。。。。）
然后复数的运算是：当$x=a+bi, y=c+di$
$$x+y=(a+c)+(b+d)i$$
$$x-y=(a-c)+(b-d)i$$
$$x \times y=(a+bi)(c+di)=ac+adi+bci+bdi^2=(ac-bd)+(ad+bc)i$$
除法怎么搞。。。。。。（以后补。。
然后我们定义复数幂：
$$e^{iu}=cos(u)+isin(u)$$
然后因为由于是指数，我们可以得到很好的性质。
关于复数还是详见算导p511吧。。我不阐述了。。
fft的具体实现也看算导p513吧，，我也不阐述了。。。
关于fft的迭代优化我也不阐述了。。。。
然后本文介绍fft的东西就完结了。。
下边是一些疑问与拓展：
我之前的疑问和暂时还有疑问的地方：
- 为什么是用复数指数幂的形式？我的解释是，，，因为根据复数幂定义能提供良好的相消引理。。这个很简单吧。。
- 为什么复数幂的形式是$e^{iu}=cos(u)+isin(u)$呢？因为周期性？
- 为什么复数做x时，赋值到复数的实部？之前解释过了，因为实数是复数的子集。
- 为什么$DFT^{-1}$后取的也是实部？同上
拓展：
- 多维的fft：对于多维多项式：$$y_{k_1, k_2, \cdots , k_d}=\sum_{j_1}^{n_1-1} \sum_{j_2}^{n_2-1} \cdots \sum_{j_d}^{n_d-1} a_{j_1, j_2, \cdots , j_d} \omega_{n_1}^{j_1 k_1} \omega_{n_2}^{j_2 k_2} \cdots \omega_{n_d}^{j_d k_d}$$我们可以对每一维单独用fft求出，然后再带入原式求下一维。认真体会。。
模板题：
将十进制数看成多项式x=10，然后系数就是所有的数，然后用fft算出乘积后的系数后进位即可。
#include#include #include #include #include #include #include #include #include
其它例题：
：同上，高精度裸题
：注意卷积的形式