拉格朗日插值法的介绍与应用

update 9.23 lagrange重心插值改进&&模板
定理：给定n+1个不同数的取值，可以唯一确定一个次数不超过n的多项式。
如何求出这个多项式可以使用拉格朗日插值法。
拉格朗日插值法：
假设我们得到了n+1个点，

定义：xj的"开关"为：

为什么称它为开关呢？因为构造使得pj(xj)=1，而带入任意xi(i不等于j)都pj=0，
这样接着构造出这个n次多项式

跟据开关的性质，我们知道Ln(xi)=yi
下面介绍拉格朗日插值法的应用。
求自然数的幂的前缀和

当k=1的时候，我们知道柿子为(n+1)*n/2，可以推广，求和柿子一定是一个k+1次。
跟据拉格朗日插值法,设答案柿子为f(n),我们知道只要求出把(0,f(0)),(1,f(1))...(k+1,f(k+1))这k+2个数带入，就可得到答案的k+1次柿子且是唯一确定的！

通过万恶的数学推导：

我们分析一下时间复杂度；
前缀+后缀积，分母两个阶乘，都是O(k)时间复杂度，剩下的问题就是求出f(0),f(1)...f(k+1)，只要我们可以快速的求出某个k次多项式的前k+1个值，那么剩下的部分可以使用拉格朗日插值法在Θ(k)的时间内完成计算。

利用拉格朗日插值的重心优化，我们可以把时间复杂度降低到O(n)

模板