文档介绍：深入探究多项式乘法的快速算法
就是一个当x=b的多项式的取值而已。但是在多项式中，x的意义仅仅是一个符号而已，ai*x^i你可以理解为ai在数组的第i个位置。
我们主定理是什么自己查），嗯，好像并没有什么卵用，常数上还因为递归的缘故比原来大了，但这并不代表我们的思路没有卵用。
现在考虑是否可以通过将式子变形来少计算几次乘积呢？这里AC和BD是必须要计算出来的乘积（思考为什么），所以现在考虑(AD+BC)
的变形，由于我们已经计算出了AC和BD，那么是否可以直接把这个结果利用上呢？先相加起来AC+BD+AD+BC=(A+B)(C+D)，所以AD+BC=(A+B)(C+D)-AC-BD，那么整个式子就变成了：
这样一来，我们只需要计算AC、BD、(A+B)(C+D)三次乘法就行了，然后进行加加减减，时间复杂度T(n)=3*T(n/2)+O(n)，解得：
这样的复杂度看起来可能有些玄学，那么它究竟是怎样的呢？举个栗子，当n=100000（一般来说十万这个数量级是O(nlogn)与O(n^2)的分界线）时，，仍然可以满足，但是已经接近极限了，再加上递归的巨大常数，是很勉强的。而当n=300000时，，已经爆掉了。虽然我们将多项式乘法通过这样的分治算法进行了优化，但仍然无法满足我们的需求。
我们可以发现这样的分治没有达到对数级别，这意味着一个坏消息：我们还没做到位，以及一个好消息：我们可以做得更好。
既然从中间分治不够完美，我们不妨退一步，从多项式的表达式中寻求规律。
从中间分治试过了，那如果我们按照奇偶性分开呢？
我们发现如果按照奇偶项分开，左右两边的形式都是一样的，而且都可以被表示成一个多项式的形式，也就是说，A(x)可以这样被表示：
那么这样的分治有什么卵用呢？答：取值的时候有用。
如果我们要将n个不同的x值代入到A(x)中，那么就会产生n个值，这样的操作叫做多项式的求值。求一个值的时间复杂度是O(n)（利用秦九韶算法），那么求n个值的时间复杂度就是O(n^2)，但我们可以从上面这个式子中发现这样一个性质：
这意味着什么？我们可以选择n/2个x值，把
n/2个x^2代入到AL和AR中，然后根据上面的性质，就能求出n个A(xi)值了，这n个A(x)的值分别是n/2个x和n/2个-x代入A(x)的值，按照这样的算法，我们可以得出这样分治求值的复杂度：
好的，现在我们成功地偏离了主题：说好的求乘积呢？不慌,不慌。
三、变换与反演
上面我们讨论到了从多项式的系数表达求出了值，也就是说我们可以快速地找到对于已知系数ai的多项式A(x)，n个不同的x值到n个取值的对应关系，即：
这像一个化学反应方程式，现在想：如果我们知道了左边的和右边的，我们是否可以求出中间的呢？也就是说如果我们知道有一个次数界为n的多项式，知道n个不同的x值以及它们代入所得的n个不同的取值，是否可以求出这个多项式的系数从而确定这个多项式呢？
这看起来像个数学题，然而我们好像做过这样的数学题：已知二次函数f(x)经过三个点，求f(x)的表达式。
这就变得有意思了吗？上面那个例子正是知道(x0,f(x0)),(x1,f(x1)),(x2,f(x3))三个点，求一个次数界为2+1=3的多项式的系数。数学老师告诉我们：这是可行的，只不过可能会有些难算。但这没什么，毕竟计算机的一个优势就在于计算速度快，现在我们关心的是这样的一个性质是否对于任意一个n都成立呢？要想严格地证明这个问题，我们就要先严格地描述这个问题。如果我们用yi这样一个直观的东西来表示A(xi)的话，上面的求值可以表示为：
上面所叙述的求值操作就是在已知X和A的情况下求Y，那么我们要求的问题就是已知X和Y来求A，那这个问题就很简单了，我们只需要求出来X的逆矩阵就行了，这样。不幸的是，不是每一个矩阵都有逆矩阵的，但幸运的是，X是必然有逆矩阵的。
像X这样有个性的矩阵当然得有个自己的名字了，它叫做范德蒙矩阵，而它的行列式是这样的：
至于如何推导……我也不知道
可以看到，如果n个xi都不相同的话，范德蒙矩阵的行列式就不为零，而我们知道矩阵有逆当且仅当其行列式不为零。
现在，我们知道了，一个次数界为n的多项式的系数与其在n个不同x值处的取值存在一一对应的关系：
既然存在这样一个一一对应的关系，那么我们就可以用值而不是系数的形式表示一个多