【目标】
如何以 (O(N log N)) 的效率将系数多项式转换为点值多项式。
【前置技能】
众所周知，(x^n=1)的根有n个，而且它们分别是(e^{frac{2πi}{n}})，即在复平面内的坐标为((cos(2πi),sin(2πi)))。
我们分别用(ω_n^0~ω_n^{n-1})来描述这n个根。而且等会我们要算的，就是多项式A在这n个点处的点值。
为了方便计算，我们设n为2的幂次。
由复数的性质可以得到一些公式：
((ω_{2n}^{2k})=ω_n^k)
((ω_n^k)^2=ω_n^{2k}=ω_{n/2}^{k})
(ω_n^{k+frac{n}{2}}=-ω_n^k)
【递归计算点值】
假设我们有一个长度为n的多项式(A(x)=a_0+a_1x...a_{n-1}x^{n-1})，现在我们设一个过程(F(A))来递归地计算(A(x))的点值多项式（而且点值的自变量就是上述n个单位复数根）。
简单地把(A(x))拆分成两个多项式，即设：
(A_0(x)=a_0+a_2x+a_4x^2...+a_{n/2-2}x^{frac{n}{2}-1})
(A_1(x)=a_1+a_3x+a_5x^2...+a_{n/2-1}x^{frac{n}{2}-1})
容易发现(A(x)=A_0(x^2)+x*A_1(x^2))
我们要求的是对于所有k，(ω_n^k) 处的点值。
且(A(ω_n^k)=A_0((ω_n^k)^2)+ω_n^k*A_1((ω_n^k)^2))
先求所有的k满足(k∈[0,n/2))
化简易得(A(ω_n^k)=A_0(ω_{frac{n}{2}}^k)+ω_n^k*A_1(ω_{frac{n}{2}}^k))
而且对于(k∈[0,n/2))，我们也可以得到
(A(ω_n^{k+frac{n}{2}})=A_0(ω_n^{2k+n})+ω_n^{k+frac{n}{2}}*A_1(ω_n^{2k+n}))
(=A_0(ω_n^{2k})-ω_n^{k}*A_1(ω_n^{2k})=A_0(ω_{frac{n}{2}}^k)-ω_n^{k}*A_1(ω_{frac{n}{2}}^k))
此时我们已经能求出所有的点值了，而且我们要用到的条件就是：
(A_0(ω_{frac{n}{2}}^k)) 和 (A_1(ω_{frac{n}{2}}^k)) (k∈[0,n/2))
容易发现这就是子问题，我们只需直接递归 (F(A_0)) 和 (F(A_1)) 即可。
由主定理，得效率为(T(N)=O(N)+2*T(frac{n}{2})=O(N log N))