自我感觉挺实用的一个算法。
也为一些题目提供了解决的思路。
插值：给一些散点，求满足这些个散点的函数（多项式），即求出这些系数
一般求一个点值，都要先得到系数，再O(n)算。求系数，高斯消元，是O(n^3)的。
但是，如果只要一个点值，这样岂不是血亏。
拉格朗日这个人比较厉害，他发明的算法，可以在不用求出具体系数的情况下，O(n^2)的计算一个位置的点值。
思想类似于互质的CRT，
对于给定n+1个点值，这个多项式最多n次的。而且，把每个横坐标带进去，xi自己的一项得到yi，别的由于分子有xi-xi，都是0
所以，这个多项式一定和实际上的多项式是一个多项式。
然后我们把要求的x带进去，就得到了函数值。
有什么用？
如果证明一个式子的函数是n次多项式的话，那么可以尝试得到n+1个点值，然后弄出这个公式，就可以计算比较大的答案。
https://blog.csdn.net/xyz32768/article/details/81233900
这个题，很大数据范围的k次方和，第一没有办法反演。第二没有规律可以找。
猜这个求和函数是一个k+1次多项式。然后带点求值，然后对目标答案的计算进行化简。
从O(n)到O(k^2)到O(klogk)（然鹅这个logk是因为点值的快速幂，后面的计算不是瓶颈23333）
突破口
1.想到是一个多项式
2.点值的取值是有讲究的，1~k+2这样连续的整点有助于预处理减少复杂度（跟自己干嘛要过不去23333）
所以，拉格朗日插值这个公式其实很整齐，
如果点值横坐标给的很好的话（支持递推），那么可以在O(n)时间求出一个值。已经非常不错了。
原文：https://www.cnblogs.com/Miracevin/p/10158752.html