是个好东西。
显然(n+1)个点值可以唯一的确定一个(n)次多项式。
那么根据多项式求点值的过程叫求值。
根据多项式点值来求多项式其他点值就是插值了。
那么现在上拉格朗日插值。
他解决的问题是：
对于给定的(n+1)个点值求出其他点在这个(n)次多项式的值。
我们尝试构造多项式(F(x))来满足(n+1)个点值。
我们发现这个多项式刚好有(n+1)项，同时考虑如何满足这些条件。
也就是说：
对于任意的(iin S)
那么我这样来构造多项式(F(x))。
观察每一项，如果当前代入的为(x_i)，那么第(i)项为(y_i),其余项均为0。
好了这样我们就构造成功了。
一般情况下我们取(x_i=i)，取值连续，这样更加便于求出其他的点值。
也就是说：
这样就可以直接代入(x)来算了对吧。
然后我考场上写出了另外一种对于任何点值均可以(O(n))插值出(1)个点值的方法(其实我插出了系数表达式)。
我们将$$prodlimits_{i=0}^{n}(x-x_i)$$这个多项式求出来。
当点值连续的时候我们还知道这个多项式等于：
这样同样也避免了直接暴力乘法的代码复杂度。
然后就是用代码实现一个叫多项式竖式除法的东西。
因为我们知道原来的多项式是(n)个子式乘在一起得到的。
那么不管取模与否(frac{prodlimits_{i=0}^{n}(x-x_i)}{x-x_i})一定是能够整除的。
这样用竖式除法就可以的到这个多项式了，竖式除法是(O(n))的。
然后对于每一个(i)，求出这个东西(frac{prodlimits_{i=0}^{n}(x-x_i)}{x-x_i})，再给每一项乘上系数(frac{y_i}{prodlimits_{j=0,j
eq i}^{n}x_i-x_j})，然后给插出来的多项式对位相加即可了。
然后我看到了一个叫重心拉格朗日插值的东西。。
好像和我的做法挺像的，只不过目的不同。
重心拉格朗日插值用于快速的(O(n))维护加入的新的点值。
而我的做法可以用于在维护出新的点值之后快速(O(n))的维护系数表达式。
我们设(G=sumlimits_{i=0}^{n}(x-x_i))
那么：
这样的话我们设：(T_i=y_iprodlimits_{j=0}^{j eq i}frac{1}{x_i-x_j})
这样每次加入一个新点(O(n))的更新(G)和每个点的(T_i)就可以了。