考虑给出 $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}
$$
就得到答案了。

分类: 文章

Qiuly

QAQ

1 条评论

TNT · 2020年5月29日 2:16 下午

stO

发表评论

电子邮件地址不会被公开。 必填项已用*标注