拉格朗日插值.
给出 $n$ 次多项式 $f(x)$ 上的 $n+1$ 个点 $(x_0,y_0),(x_1,y_1),\dots ,(x_n,y_n)$ .
则对于没有给出的 $f(x)$ 可以表示为
$$
f(x)=\sum_{i=0}^n y_i\cdot \prod_{j\neq i} \frac{x-x_j}{x_i-x_j}
$$
Loj 165 拉格朗日插值 1
对已经加入的每个点 $(x_i,y_i)$ ,维护一个
$$
t_i=y_i\cdot \prod_{j\neq i} \frac{1}{x_i-x_j}
$$
加入新点时,需要计算这个点的 $t$ ,以及修改之前所有点的 $t$ .
询问时,先计算一个 $prod=\prod (x-x_j)$ , 答案就是 $\sum_{i} t\cdot \frac{prod}{x-x_i}$ .
每次将 $x-x_i$ 的逆元一起求出,时间复杂度可以做到 $O(n^2+n\log P)$ .
比较懒,就写了复杂度 $O(n^2\log P)$ 的做法.
注意要特判询问的 $x$ 的点值已经给出的情况.
Loj 166 拉格朗日插值 2
给出的 $x$ 是连续的,于是第 $i$ 个询问可以变成
$$
\begin{aligned}
f(m+i)&=\sum_{j=0}^n y_j\cdot \prod_{k\neq j} \frac{m+i-k}{j-k} \\
&=\frac{(m+i)!}{(m+i-n-1)!}\cdot \sum_{j=0}^n \frac{y_j\cdot (-1)^{n-j}}{j!\cdot (n-j)!\cdot (m+i-j)} \\
&=\frac{(m+i)!}{(m+i-n-1)!}\cdot \sum_{j=0}^n \frac{y_j\cdot (-1)^{n-j}}{j!\cdot (n-j)!} \cdot \frac{1}{m-n+(n+i-j)}
\end{aligned}
$$
前面的系数是一个下降幂的形式,可以依次求出.
可以设
$$
A(i)=\frac{y_i\cdot (-1)^{n-i}}{i!\cdot (n-i)!} \\
B(i)=\frac{1}{m-n+i}
$$
这样后面就是 $\sum A(j)\cdot B(n+i-j)$ 了,用 NTT 做卷积,$f(m+i)$ 就存在 $n+i$ 的位置上了.
时间复杂度可以做到 $O(n\log n)$ .比较懒,就写了 $O(n\log P)$ 的做法.