拉格朗日插值法基于这个事实：\(n\)个点可以唯一确定一个\(n-1\)次多项式。
拉格朗日插值法
设\(f(x)\)是个\(n\)次多项式
\[
f(x_0)=\sum_{i=0}^{n}y_i\prod_{j\not = i}\frac {x_0-x_j} {x_i-x_j}
\]
可以发现对于所给的点都可以利用该多项式正确地求出（考虑\(\prod_{j\not =i}\frac {x_0-x_j} {x_i-x_j}\)这个式子，\(x_0=x_i\)时，其值恰好为\(1\)，然后对于\(x_0\not = x_i\)时，其值恰好为\(0\)）
复杂度是\(O(n^2)\)的。
取值连续时的拉格朗日插值法
因为只需要任意\(n+1\)个不同点就可以确定一个\(n\)次多项式，所以很多时候为了方便取的任意\(n+1\)个点其实是连续的\(1,2,3,...,n+1\)。
那么令\(x_i=i\)，上述式子可以写成
\[
f(x_0)=\sum_{i=0}^{n}y_i\prod_{j\not = i}\frac {x_0-j} {i-j}
\]
\(\prod_{j\not = i}\frac {x_0-j} {i-j}=\frac {\prod_{j<i} x_0-j\prod_{j>i}x_0 - j} {i!(n-i)!}\)
那么预先维护出关于\(x_0\)的前缀积\(pre\)和后缀积\(suf\)，原式即可化为
\[
f(x_0)=\sum_{i=0}^{n}y_i \frac {pre[i-1]\times suf[i+1]} {i!(n-i)!}
\]
于是复杂度降为\(O(n\log n)\)，瓶颈在逆元，可以利用逆元的线性求法做到\(O(n)\)。
应用：自然数幂和
求\[\sum_{i=1}^n i^k\]
\(1\le n\le 10^9, 1\le k \le 10^6\)
\(\sum i^k\)是一个\(k+1\)次多项式。所以拉格朗日插值插出这个多项式，然后代入\(n\)即可。
