【算法】拉格朗日插值法 —Qiuly

考虑给出 $n$ 对 $(a_i,b_i)$ ，以及一个 $n-1$ 次多项式 $f(x)$ 满足 $f(a_i)=b_i$ ，要求对于一个 $x’$ ，求出 $f(x’)$ 。

然后有这么个式子：
$$
f(x)\equiv f(x_0)\bmod{x-x_0}
$$
*这个式子同样在多项式多点求值中用到了。

等于现在我们需要求的是这个：
$$
\begin{cases}
f(x)\equiv b_1\bmod{x-a_1}\\
f(x)\equiv b_2\bmod{x-a_2}\\
\cdots\\
f(x)\equiv b_n\bmod{x-a_n}\\
\end{cases}
$$
让我们回忆一下 $\rm{CRT}$ (中国剩余定理) ：

首先令 $M_i=\prod_{j\not=i}a_j$ ，那么显然有：
$$
\forall j\not=i,M_i\equiv 0\bmod{a_j}\\
\forall j\not=i,M_i\cdot C\equiv 0\bmod{a_j}\\
M_i\equiv b_i\bmod{a_i}
$$
其中 $C$ 是任意常数。

所以只需要满足 $M_i\cdot C\equiv b_i\bmod{a_i}$ ，令 $C$ 为 $M_i$ 在 $\bmod{a_i}$ 意义下的逆元即可，这样就可以得到：
$$
Ans=\sum_{i=1}^{n} M_i\cdot M_i^{-1,a_i}\cdot b_i
$$
这样就没了。

这样下来的话和 $\rm{CRT}$ 也差不多，令：
$$
M_i(x)=\prod_{j\not=i}(x-a_i)\\
F(x)=\sum_{i=1}^{n}M_i(x)\cdot M_i(x)^{-1,(x-a_i)}\cdot b_i
$$
然后，因为有：
$$
f(x)\equiv f(x_0)\bmod{x-x_0}\\
M_i(a_i)=\prod_{j\not=i}(a_i-a_j)
$$
就可以得到：
$$
M_i(x)\equiv M_i(a_i)\bmod{x-a_i}\\
M_i(x)\equiv \left(\prod_{j\not=i}(a_i-a_j)\right)\bmod{x-a_i}
$$
这样的话回到原式：
$$
\begin{aligned}
F(x)&=\sum_{i=1}^{n}M_i(x)\cdot M_i(x)^{-1,(x-a_i)}\cdot b_i\\
&=\sum_{i=1}^{n}\frac{M_i(x)\cdot b_i}{\prod_{j\not=i}(a_i-a_j)}\\
&=\sum_{i=1}^{n}b_i\cdot\frac{\prod_{j\not=i}(x-a_j)}{\prod_{j\not=i}(a_i-a_j)}
\end{aligned}
$$
就得到答案了。