给定两个多项式 f(x) 和 g(x)，如何高效的求他们的乘积
暴力展开是最容易想到的，将两个多项式的每一项分别相乘，最后合并同类项，最终得到结果h(x)
这样计算的时间复杂度为O(n^2)，当n=1,000,000 时，计算量达 10^12 次
我们知道，一个 n-1 次多项式可以由任意 n 个不同点唯一确定。
如果能在 n 个点 x_i 上快速计算出：f(x_i) 和 g(x_i)，
那么乘积多项式在这些点上的值就是：h(x_i) = f(x_i) g(x_i)，
再通过拉格朗日插值法得到 h(x) 的系数形式，
但是求插值多项式的时间复杂度仍为 O(n^2)
采用分治思想，将多项式按奇偶次幂分离
于是f(x)拆解为两个多项式f_e(x)和f_o(x)
分别带入 x=1和x=-1，可以看到计算一次 f_e(1) 和 f_o(1)，就能同时得到 f(1) 和 f(-1) 两个点值
f_e(x) 和 f_o(x) 也可以按照相同的方式按奇偶次幂分离
分别带入 x=1和 x=-1，可以得到四个点值
我们知道 f_e(1) 和 f_o(1) 可以推出 f(1) 和 f(-1) 的值，那么 f_e(-1) 和 f_o(-1) 有什么用呢
注意观察 f(x) = f_e(x^2) + x * f_o(x^2)
x^2 =1时，也就是 f_e(1) 和 f_o(1) 可以得到 f(1) 和 f(-1) 两个点值
x^2 =-1时，也就是 f_e(-1) 和 f_o(-1) 可以得到 f(i) 和 f(-i) 两个点值
孩子们，是复数，我们有救了
这样的话，我们可以利用 f_e(x) 和 f_o(x) 两个函数分别取 x=1和 -1 得到 f(x) 的四个点值
将 n 个点求值问题，分治为两个 n/2 的求值问题，然后求 n个值。总递归层数为log(n)，时间复杂度O(nlogn)！
如何求更多的点值呢？
我们可以尝试继续将 i 和 -i 开平方，得到左侧的树状图
利用欧拉公式，每层的点值写成指数形式，可以均匀地在排布在复平面单位圆上
可以观察到这些点值，有这样指数约分和对称取负两个性质，令 w_n 为单位根，将其表述为这样两个公式
将这两个公式继续带入 f(x) 并化简，这就是算法实现中最重要的两步
让我们回顾整个过程
首先将多项式系数按奇偶次幂分离为两组，在每组只剩两个点时，通过加减运算得到 f_e(x) 和 f_o(x) 在 x=1和-1 处的值
同样的 f(x) 在 单位根 w_n^k 和 w_n^{k+n/2} 处的点值可以由 f_e(w_{n/2}^k) 与 f_o(w_{n/2}^k) 乘以 单位根 w_n^k 加减运算
根据以上计算过程，可以写成 python 代码
现在有了 n 个点值，如何还原为原多项式？
将单位根代入多项式并写成矩阵形式，可以看到每个点值都由一组单位根与系数乘积之和可得，这个过程被成为 离散傅里叶变换 DFT
其逆变换只需把单位根 w_n 逆也就是取倒数，然后整体除以 n