拉格朗日插值

有一个一元 $k$ 次方程，给定互不相同的 $x_1,x_2,\dots,x_{k+1}$，以及与之对应的 $f(x_1),f(x_2),\dots,f(x_{k+1})$。

请求出这个 $k$ 次方程，一般情况下只需要对于另一个 $x$ 求出对应的 $f(x)$ 就可以了。

上文的高斯消元给了一种非常好的解法，就是这个方程可以得到一个唯一解，把 $k+1$ 元方程列出来求解即可，时间复杂度 $O(k^3)$，十分不优。

接下来介绍一种 $O(k^2)$ 的做法，但是根据实现和性质不同可以做到 $O(k)$。

先看这个公式：

$$
f(x) = \sum_{i=1}^{k+1} f(x_i) \times \dfrac{\prod_{j \ne i}(x-x_j)}{\prod_{j \ne i}(x_i-x_j)}
$$

目前先记住这个公式，后面讲多项式除法的时候会有更详细的证明。

如果 $x$ 数组是我们选的并且是连续整数，那么我们可以 $O(k)$ 插值。

具体方法就是下面的 $\prod_{j \ne i}(x_i-x_j)$ 可以转化为两个阶乘相乘，这个可以 $O(k)$ 预处理。

然后上面的 $\prod_{j \ne i}(x-x_j)$ 就不需要连续整数这个限制，预处理 $\prod(x-x_j)$ 的前后缀积，调用的时候把第 $i$ 项排除掉即可。

这样的话即可做到 $O(k)$ 求某多项式任意点的值，同时小学数学也告诉我们 $k+1$ 个点唯一确定一个 $k$ 次函数，并且这个函数有唯一解，故算法正确。

最后就是注意取模和逆元的问题，特别的，有 $f(x)\equiv f(x \bmod p)\pmod p$，这样也能解决大部分模数是质数的问题了。