多项式

这个东西应该在很久之前就要学的结果被鸽到了现在。 拉格朗日插值解决的是一类给定多项式的点值表示让你求另一个点的函数值的问题。 据此，我们只要能找到一个多项式的点值表示，我们便可以求出这个多项式上任意一点的值

但有时用 "长除" 会比较合适（与数字长除法相似） 来帮你记住，想象：妈妈抱着孩子在身体上面。 把分子的第一项除以分母的第一项，把结果放进答案里。 检测答案： 把答案乘以下面的多项式，结果应该是上面的多项式： 上面的例子刚好可以整除，但并不是时常都这样！余项是除完之后剩下的项

那么就可以通过多次对 加上 的倍数来降低 的次数。 问题转化成了快速地求 ，只要将 普通快速幂 中的乘法与取模换成 多项式乘法 与 多项式取模 就可以在 的时间复杂度内解决这个问题了。 发现若能将两边的 消去后得到多项式 满足 其中 为一个 的零矩阵