拉格朗日插值

具体证明见wikipedia
## 拉格朗日插值 如果给一个度数为\(n\)的多项式的\(n+1\)个点\((x-i,y-i)\)，那么我们可以用拉格朗日插值将求出这个多项式在所有点的取值。

假设\(x-i\)互不相同，\(F(k)=\sum\limits_{i=0}^{deg} y-i \ell-i(k)\)

其中\(\ell-i\)是拉格朗日基本多项式，\(\ell-i(k)=\prod\limits_{j=0,i\neq j}^{deg}\frac{k-x-j}{x-i-x-j}\)

这个\(\ell\)有什么特点呢？
对于\(\forall j\neq i\)，\(\ell-i(x-j)=0，而\)-i(x-i)=1$。
代值进去即可验证。

所以\(\forall x-i,F(x-i)=\sum\limits_{i=0}^{deg} y-i \ell-i(x-i)=y-i\)，一共有\(deg+1\)个点，所以能确定一个多项式。
时间复杂度\(\mathjaxcal{O}(n^2)\)

重心拉格朗日插值

每一次都算\(\ell\)好像很慢。
令\(\ell(x)=(x-x-1)(x-x-2)...(x-x-n)\)
\(w-i=\frac{1}{\prod\limits_{j=0,i\neq j}^{deg}(x-i-x-j)}\)

则\(\ell-i(x)=\frac{\ell(x)}{x-x-i}w-i\)
\(F(x)=\sum\limits_{i=0}^{deg}y-i\ell-i(x)\)
\(F(x)=\ell(x)\sum\limits_{i=0}^{deg}y-i\frac{w-i}{x-x-i}\)

\(w-i\)称为\(i\)的重心，每次加入新点时可以\(\mathjaxcal{O}(n)\)算新重心，计算\(F\)也是\(\mathjaxcal{O}(n)\)的。

当然初始化重心是\(\mathjaxcal{O}(n^2)\)