//最近突然发现博客园支持( mLaTeX)，非常高兴啊！
话说离省选只有不到五天了还在学新东西确实有点逗……
切到正题，FFT还是非常神奇的一个东西，能够反直觉地把两个多项式相乘的时间复杂度降到(O(n log n))。
首先，多项式的表示方法有两种：
第一种是系数表示法(sum_{i=0}^{n-1}a_i x^i)，就是正常的表达一个多项式的办法。
第二种比较神奇，是点值表示法，就是用(n)个点((x_i,y_i))来表示一个多项式，也就是用两个列向量(x)和(y)来表示一个多项式。
将两个多项式表示成系数表示法直接相乘需要(O(n^2))的时间，而将两个用点值表示法的多项式相乘却只用(O(n))的时间（将两个多项式的(y)向量的每一维分别相乘即可）。
而FFT干的事情就是在(O(nlog n))的时间内将多项式从系数表示法转化成点值表示法，或者是将点值表示法转化为系数表示法。
从直觉上看，列向量(x)的每一维的随便乱取显然是不靠谱的，为了保证优越的复杂度，我们引入一个神奇的工具——单位复根。
================未完待续================
P.S. 省选居然能考到这种鬼东西！运气真是太好了！