库存
一、概念
FFT：快速傅里叶变换
DFT：离散傅里叶变换
二、多项式的表示
系数表示法：
点值表示法：所有x互不相同
系数表示法的优点：求值$O(n)$，加法$O(n)$；缺点：乘法$O(n^2)$
点值表示法的优点：乘法$O(n)$
三、思想
于是FFT的主要过程就出来了：
1、加长数组，到2的幂次长度，设为n
2、求值，两多项式在n个点的取值
3、逐点相乘
4、差值，求系数
四、引入单位复数根
对于n个点，如果随便选还是$O(n^2)$求的，如果这n个点选择单位复数根，将会$O(nlogn)$求出。
1、复数
$a+bi$，a为实部，bi为虚部。
加法：$(a+bi)+(c+di)=(a+c)+(b+d)i$
乘法：$(a+bi) imes (c+di) = (ac-bd) + (ad+bc)i$
2、复平面
$w^n=1$,w为复数
一共有n个，为k=0,1,
未完