多项式的表示方法 系数表示法：
$$f(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n$$
点值表示法：$$f(x)=\{(x_0,f(x_0)),(x_1,f(x_1)),(x_2,f(x_2)),\cdots,(x_n,f(x_n))\}$$
多项式乘法与DFT设我们已知两个点值表示法的多项式$f(x),g(x)$：
$$f(x)=\{(x_0,f(x_0)),(x_1,f(x_1)),(x_2,f(x_2)),\cdots,(x_n,f(x_n))\}$$
$$g(x)=\{(x_0,g(x_0)),(x_1,g(x_1)),(x_2,g(x_2)),\cdots,(x_n,g(x_n))\}$$
设两个多项式相乘和结果是$h(x)$：
$$h(x)=\{(x_0,f(x_0)g(x_0)),(x_1,f(x_1)g(x_1)),(x_2,f(x_2)g(x_2)),\cdots,(x_n,f(x_n)g(x_n))\}$$
是不是感觉多项式乘法能$O(n)$过。 你想多了。。。 如何将系数转点值？ 朴素的系数转点值叫做DFT（离散傅里叶变换），点值转系数叫做IDFT（离散傅里叶逆变换），计算式DFT，IDFT仍然需要$O(n^2)$。 难道就没有其他办法了吗？ 当然有。FFT和IFFT闪亮登场，我们只要$O(n\log(n))$，就可以完成双方的转换。 单位复根事实上，对于多项式系数转点值，我们可以随意取n个不同的x，但这种暴力法太慢。但我们可以取一些神奇的点，将满足$\omega ^n=1$的值作为带入的点。这就是离散傅里叶变换的神奇之处了，取的点不是实数，而是复数。
求解$\omega ^n=1$对于所有的解都可以在下图的圆上得到：
以$n=8$为例，即$\omega ^8=1$
将一个圆分成8份，我们可以得到8个解：$\omega _8^0,\omega _8^1,\omega _8^2,\omega _8^3,\omega _8^4,\omega _8^5,\omega _8^6,\omega _8^7$
即：$$\omega _n^k=\cos{\frac{2\pi }{n}k}+i\sin{\frac{2\pi }{n}k}$$
性质：$(1)~~\omega _{an}^{ak}=\omega _n^k$
$(2)~~\omega _n^{k-\frac n2}=-\omega _n^k$
$(3)~~\omega _n^k=\omega _n^{k\%n}$
$(4)~~(\omega _n^k)^p=\omega _n^{kp}$
FFT（快速傅里叶变换）我们以多项式$f(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+a_6x^6+a_7x^7$为例：
$\begin{align*} f(x)&=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5+a_6x^6+a_7x^7 \\ &=a_0+a_2x^2+a_4x^4+a_6x^6+x(a_1+a_3x^2+a_5x^4+a_7x^6) \end{align*}$
$令A^{[0]}(x)=a_0+a_2x+a_4x^2+a_6x^3,A^{[1]}(x)=a_1+a_3x+a_5x^2+a_7x^3$
$则f(x)=A^{[0]}(x^2)+xA^{[1]}(x^2)$
$\begin{align*} &f(\omega _8^0)=A^{[0]}(\omega _8^0)+\omega _8^0A^{[1]}(\omega _8^0) =A^{[0]}(\omega _4^0)+\omega _8^0A^{[1]}(\omega _4^0) \\ &f(\omega _8^1)=A^{[0]}(\omega _8^2)+\omega _8^1A^{[1]}(\omega _8^2) =A^{[0]}(\omega _4^1)+\omega _8^1A^{[1]}(\omega _4^1) \\ &f(\omega _8^2)=A^{[0]}(\omega _8^4)+\omega _8^2A^{[1]}(\omega _8^4) =A^{[0]}(\omega _4^2)+\omega _8^2A^{[1]}(\omega _4^2) \\ &f(\omega _8^3)=A^{[0]}(\omega _8^6)+\omega _8^3A^{[1]}(\omega _8^6) =A^{[0]}(\omega _4^3)+\omega _8^3A^{[1]}(\omega _4^3) \\ &f(\omega _8^4)=A^{[0]}(\omega _8^8)+\omega _8^4A^{[1]}(\omega _8^8) =A^{[0]}(\omega _4^0)-\omega _8^0A^{[1]}(\omega _4^0) \\ &f(\omega _8^5)=A^{[0]}(\omega _8^{10})+\omega _8^5A^{[1]}(\omega _8^{10})=A^{[0]}(\omega _4^1)-\omega _8^1A^{[1]}(\omega _4^1) \\ &f(\omega _8^6)=A^{[0]}(\omega _8^{12})+\omega _8^6A^{[1]}(\omega _8^{12})=A^{[0]}(\omega _4^2)-\omega _8^2A^{[1]}(\omega _4^2) \\ &f(\omega _8^7)=A^{[0]}(\omega _8^{14})+\omega _8^7A^{[1]}(\omega _8^{14})=A^{[0]}(\omega _4^3)-\omega _8^3A^{[1]}(\omega _4^3) \end{align*}$
$\begin{align*} A^{[0]}(x)&=a_0+a_2x+a_4x^2+a_6x^3 \\ &=a_0+a_4x^2+x(a_2+a_6x^2) \end{align*}$
令$B^{[0]}(x)=a_0+a_4x,B^{[1]}(x)=a_2+a_6x$
则$A^{[0]}(x)=B^{[0]}(x^2)+xB^{[1]}(x^2)$
$\begin{align*} &A^{[0]}(\omega _4^0)=B^{[0]}(\omega _4^0)+\omega _4^0B^{[1]}(\omega _4^0)=B^{[0]}(\omega _2^0)+\omega _4^0B^{[1]}(\omega _2^0) \\ &A^{[0]}(\omega _4^1)=B^{[0]}(\omega _4^2)+\omega _4^1B^{[1]}(\omega _4^2)=B^{[0]}(\omega _2^1)+\omega _4^1B^{[1]}(\omega _2^1) \\ &A^{[0]}(\omega _4^2)=B^{[0]}(\omega _4^4)+\omega _4^2B^{[1]}(\omega _4^4)=B^{[0]}(\omega _2^0)-\omega _4^0B^{[1]}(\omega _2^0) \\ &A^{[0]}(\omega _4^3)=B^{[0]}(\omega _4^6)+\omega _4^3B^{[1]}(\omega _4^6)=B^{[0]}(\omega _2^1)-\omega _4^1B^{[1]}(\omega _2^1) \\ \end{align*}$
$\begin{align*} B^{[0]}(x)&=a_0+a_4x \\ &=a_0+xa_4 \end{align*}$
$\begin{align*} &B^{[0]}(\omega _2^0)=a_0+\omega _2^0 a_4 \\ &B^{[0]}(\omega _2^1)=a_0+\omega _2^1 a_4=a_0-\omega _2^0 a_4 \\ \end{align*}$
我只写了二叉树一直往左走的情况，全部情况如下图：
对于上面的方程组我们可以用矩阵来表示：
$$\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & \omega_8^1 & \omega_8^2 & \omega_8^3 & \omega_8^4 & \omega_8^8 & \omega_8^6 & \omega_8^7 \\ 1 & \omega_8^2 & \omega_8^4 & \omega_8^6 & \omega_8^8 & \omega_8^{10} & \omega_8^{12} & \omega_8^{14} \\ 1 & \omega_8^3 & \omega_8^6 & \omega_8^9 & \omega_8^{12} & \omega_8^{15} & \omega_8^{18} & \omega_8^{21} \\ 1 & \omega_8^4 & \omega_8^8 & \omega_8^12 & \omega_8^{16} & \omega_8^{20} & \omega_8^{24} & \omega_8^{28} \\ 1 & \omega_8^5 & \omega_8^{10} & \omega_8^{15} & \omega_8^{20} & \omega_8^{25} & \omega_8^{30} & \omega_8^{35} \\ 1 & \omega_8^6 & \omega_8^{12} & \omega_8^{18} & \omega_8^{24} & \omega_8^{30} & \omega_8^{36} & \omega_8^{42} \\ 1 & \omega_8^7 & \omega_8^{14} & \omega_8^{21} & \omega_8^{28} & \omega_8^{35} & \omega_8^{42} & \omega_8^{49} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ a_4 \\ a_5 \\ a_6 \\ a_7 \end{bmatrix} = \begin{bmatrix} f(\omega _8^0) \\ f(\omega _8^1) \\ f(\omega _8^2) \\ f(\omega _8^3) \\ f(\omega _8^4) \\ f(\omega _8^5) \\ f(\omega _8^7) \\ f(\omega _8^7) \end{bmatrix}$$