拉格朗日插值

用处

设 $f(x)$ 是一个 $n$ 次多项式，现在知道 $x + 1$ 个点满足多项式 $f(x)$ ，求这个这个多项式上的任意的另一个点。

方法

​ 对于大多对于拉格朗日的讲解都过于的复杂，这里有一种较为简单的理解：

​ 对于已知的 $x + 1$ 个的点，我们可以依次使得 $x_i$ 的 $f(x_i) = 1$ 其余的 $f(x_i)$ 都等于 $1$ 。于是我们可以得到 $x + 1$ 个方程，然后就可以求解了！

公式

$f(k) = \sum^{n}_{i = 1} y_i \prod_{j \ne i} \dfrac{k - x_j}{x_i - x_j}$

证明：

由多项式除法可得：

$f(x) \equiv f(a) (\mod (x - a))$

这样我们就可以列一个关于 $f(x)$ 的多项式线性同余方程组：

$\begin{cases} f(x)\equiv y_1 \pmod{(x - x_1)}\\ f(x)\equiv y_n\pmod{(x - x_2)}\\\cdots\\f(x)\equiv y_n\pmod{(x - x_n)} \end{cases}$

我们根据中国剩余定理，有：

$M = \prod_{i = 1}^n{(x - x_1)}, m_i = \dfrac M{x - x_i} = \prod_{j\ne i}{(x - x_j)}$

则 $m_i$ 模 $(x - x_i)$ 意义下的逆元就是：

$m_i ^ {-1} = \prod_{j \ne i} \dfrac 1{x_i - x_j}$

所以就有：

$f(x) \equiv \sum^n_{i = 1}y_i m_im_i ^{-1} \equiv \sum ^n_{i = 1}y_i \prod_{j\ne i}\dfrac{x - x_i}{x_i - x_j}\pmod M$

所以在模意义下 $f(x)$ 就是唯一的，即：

$f(k) = \sum^{n}_{i = 1} y_i \prod_{j \ne i} \dfrac{k - x_j}{x_i - x_j}$

QED.

时间复杂度

$O(n^2)$