【算法】拉格朗日插值法 —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}$$
就得到答案了。