我们知道，对于一个 \(k\) 次多项式，我们只需知道它在 \(k+1\) 个点上的取值，就能求出这个多项式。我们可以列方程求出每一个的系数，但是这样的时间复杂度是 \(n^3\) 的，所以我们使用一些别的方法来求出对于某个点的值。
拉格朗日插值：
设已知平面内的 \(n\) 个点，要求这 \(n\) 个点的 \(n-1\) 次的函数。我们将每个点 \(i\) 在 \(x\)轴 上的投影设为 \(i'\) ，我们将每个点 \(i\) 与其余点的投影设一个函数 \(f_i(x)=a*\prod_{j=1,j!=i}^n (x-x_j)\) ，其中 \(a\) 是常数，使用交点式来表达一个函数。将点 \((x_i,y_i)\) 代入后，可以求出 \(a=\frac{y_i}{\prod_{j=1,j!=i}^n (x_i-x_j)}\) ，于是函数 \(f_i(x)\) 的表达式为：
\[f_i(x)=y_i*\prod_{j=1,j!=i}^{n}\frac{x-x_j}{x_i-x_j} \]然后最终这 \(n\) 个点的函数 \(f(x)=\sum_{i=1}^n f_i(x)\) ，即：
\[f(x)=\sum_{i=1}^n y_i*\prod_{j=1,j!=i}^{n}\frac{x-x_j}{x_i-x_j} \]这个就是拉格朗日插值的式子了，时间复杂度为 \(O(n^2)\) 。
我们可以使用多项式将其优化至 \(O(n log^2\ n)\) 。
横坐标连续的拉格朗日插值：
在一些题目中，如果给定的点有上面的这种性质 或 题目并没有限制点的横坐标的话，那么我们可以将时间复杂度优化至 \(O(n)\) 。
我们假设这些点的横坐标为 \(1...n\) ，然后原来的式子就可以化成：
\[f(x)=\sum_{i=1}^n y_i*\prod_{j=1,j!=i}^{n}\frac{x-j}{i-j} \]将分子分母分开来处理 \(\prod\) ：
\[\prod_{j=1,j!=i}^{n}x-j=\frac{\prod^{n}_{j=1}(x-j)}{x-i} \]这里可以预处理上面的积，然后除掉 \((x-i)\) 或 处理出以 \(i\) 为分界点的 \((x-j)\) 的前后缀的积。
分母：
\[\prod_{j=1,j!=i}^{n}i-j=(i-1)!*(-1)^{n-i}*(n-i)! \]然后总的式子就变成了：
\[f(x)=\sum_{i=1}^n y_i*\prod_{j=1,j!=i}^{n}\frac{x-j}{i-j}=\sum_{i=1}^n(-1)^{n-i}* y_i*\frac{\prod_{j=1}^n (x-j)}{(x-i)*(i-1)!*(n-i)!} \]预处理阶乘的倒数就好了。
标签：拉格朗,frac,个点,插值,sum,笔记,prod From： https://www.cnblogs.com/Cyanwind/p/18355777