拉格朗日插值

点值与插值

我们定义一个多项式 $P$ 的点值为数对 $(x,y)$，满足 $P(x)=y$。

定理：对于任意 $n+1$ 个不同的点值，存在唯一的 $n$ 次多项式 $P$ 符合这些点值。

证明：

设 $n+1$ 个不同点值为 $(x_i,y_i),\ i\in \{0,1\dots n\}$，设多项式 $P(x)=\sum_{i=0}^n a_ix^i$ 符合这些点值。

将所有点值带入，可得未知数为 $a_j$ 的线性方程组 $\sum_{j=0}^n x_i^ja_j=y_j,\ i\in\{0,1\dots n\}$。

则该线性方程组的系数矩阵如下： $$ \begin{pmatrix} x_0^0 & x_0^1 & \cdots & x_0^n \ x_1^0 & x_1^1 & \cdots & x_1^n \ \vdots & \vdots & \ddots & \vdots \ x_n^0 & x_n^1 & \cdots & x_n^n \end{pmatrix} $$ 这是一个典型的范德蒙德矩阵，其行列式为 $\prod_{i<j} (x_j-x_i)$，当点值均不同时，行列式值不为 0，因此系数矩阵满秩，该线性方程组有唯一解，因此 $P$ 存在且唯一。 $\blacksquare$

我自己的补充：关于范德蒙德行列式的证明，可通过一系列的初等变换将矩阵的第一行和第一列除了左上角是 $1$ 以外都变成 $0$，而右下角又是一个范德蒙德矩阵。这样递归·地就能求出行列式。

我们称还原这个多项式的过程为插值。

拉格朗日插值（数学上）

定义：给定 $n+1$ 个不同的点值 $(x_i,y_i),\ i\in \{0,1\dots n\}$，称其拉格朗日插值多项式为 $P(x)=\sum_{i=0}^ny_i\prod_{j\not =i}\frac{x-x_j}{x_i-x_j}$。

定理：给定 $n+1$ 个不同的点值 $(x_i,y_i),\ i\in \{0,1\dots n\}$，其拉格朗日插值多项式符合这些点值。

证明：不难验证。$\blacksquare$

拉格朗日插值的核心思想在于构造一组多项式 $l_i$ 满足 $l_i(x_j)=\delta_{ij}$，其中 $\delta_{ij}$ 称为克罗内克记号，其含义为 $\delta_{ij}=[i==j]$。

具体构造方法：

首先对于一个固定的 $x_i$，我可以通过多项式因子 $x-x_j$ 将其他所有 $x_j$ 的点值变为 0，因此我们能构造出多项式 $\prod_{j\not =i} (x-x_j)$ 使得其他 $x_j$ 出取值均为 0。
此时在 $x_i$ 处取值为 $\prod_{j\not =i} (x_i-x_j)$，这是一个定值，因此将刚才的多项式除这个定值即可得到 $l_i(x)=\prod_{j\not =i}\frac{x-x_j}{x_i-x_j}$。

这一组多项式 $l_i$ 被称为拉格朗日插值基函数。

则剩下的构造就比较简单了，将这些基函数乘上对应的 $y_i$ 再相加即可得到拉格朗日插值多项式。

拉格朗日插值（OI 中）

在 OI 中，描述多项式一般有两种办法，一个是维护对应系数，称为系数表示法，另一个是维护若干点值，称为点值表示法。

前者便于求点值，但不便于进行多项式运算（卷积），而后者更易于进行多项式运算。

拉格朗日插值在 OI 中可以用于将点值表示法转换为系数表示法：

每次暴力维护 $\prod_{j\not =i} (x-x_j)$ 的总复杂度是 $O(n^3)$。
但观察到预处理出 $\prod (x-x_j)$ 然后在每个 $i$ 处除 $x-x_i$ 即可做到 $O(n^2)$ 复杂度。

拉格朗日插值在 OI 中更大的应用在于不显示的求出原多项式的系数，而直接求多项式在另外某个点的值：

对于该多项式在另一点 $x'$ 处的取值，直接使用公式 $P(x')=\sum_{i=0}^ny_i\prod_{j\not =i}\frac{x'-x_j}{x_i-x_j}$ 的复杂度是 $O(n^2)$。
但对于一些特殊情况，拉格朗日插值可以做到更快的复杂度，例如给定点值的 $x$ 是连续的情况：
若给定点值连续，例如给出了 $l\sim r$ 的若干点值 $y_i$，则有如下推导： $$ \begin{align} P(x') & =\sum_{i=l}^r y_i\prod_{j=l}^{{i-1}\frac{x'-j}{i-j}\prod_{j=i+1}}r\frac{x'-j}{i-j} \ & = \sum_{i=l}^r y_i\frac{\prod_{j=l}^r (x'-j)}{(x'-i)(i-l)!(-1)^{r-i}(r-i)!} \ & = \prod_{j=l}^r (x'-j)\sum_{i=l}^r(-1) \end{align} $$}\frac{y_i}{(x'-i)(i-l)!(r-i)!

此时只需要预处理阶乘、阶乘逆元和 $x'-i$ 逆元即可，复杂度 $O(n)$。

例题

例题 - luogu P4781

模板题。

例题 - luogu CF622F

经典结论。

$\sum_{i=1}^n i^k$ 是关于 $n$ 的 $k+1$ 次多项式，用上面说的连续点值优化拉插即可。

例题 - luogu P4463

拉插优化 DP。

题解：

首先观察到可以将 $a$ 排个序，这样只需要统计所有单调上升的序列即可，最后需要将答案乘上一个 $n!$。

其次考虑 DP，直接设 $f_{i,j}$ 表示第 $i$ 位是 $j$ 的答案，则有递推式 $f_{i,j}=j\times \sum_{k<j} f_{i-1,k}$。

我们打个表发现 $f_{1,j}=j$，$f_{2,j}=\frac12j^2(j-1)$，大胆猜测 $f_{i,j}$ 为关于 $j$ 的 $2i-1$ 次多项式，下面来证明：

首先初始条件 $f_{1,j}$ 为关于 $j$ 的一次多项式。
我们发现其实从 $i-1$ 到 $i$ 的转移相当于先做一次前缀和，再做一次按位乘 $j$。我们知道前缀和会让多项式次数 +1，按位乘 $j$ 就是乘一个自变量，也是让多项式次数 +1，因此如果 $f_{i-1,j}$ 为关于 $j$ 的 $2i-3$ 次多项式，那么 $f_{i,j}$ 即为关于 $j$ 的 $2i-1$ 次多项式。

所以直接维护每一个 $i$ 前 $2n-1$ 项的值，在最后一个 $i$ 处拉插出 $k$ 的结果即可，别忘了最后乘 $n!$。

例题 - luogu P3643

拉插优化 DP + 分段。

题解：

考虑 DP，直接设 $f_{i,j}$ 表示第 $i$ 为是 $j$ 的答案，则有递推式 $f_{i,j}=\sum_{k=0}^{j-1} f_{i-1,k}$，我们发现这是一个经典的求前缀和，让多项式次数 +1 的操作，因此考虑拉插。

但我们发现本道题有 $a_i$ 与 $b_i$ 的限制，这样有很多地方的值都会变成 0，那么剩下来的那一段里还是一个多项式吗？

观察到我们可以先将 $a_i$ 和 $b_i$ 离散化，这样每一段里的转移形如 $f_{i,j}=\sum_{k=l}^j f_{i-1,k}+\sum_{k=0}^{l-1}f_{i-1,k}$，后者对于这一段来说是一个常数，因此每一段里依旧是一个多项式。

所以我们对于每一段维护 $n$ 个点值即可，段之间的贡献直接用一次拉插来求。最后一次前缀和求答案也可以当作 $n+1$ 次多项式插值来求。

例题 - CCPC重庆 2024 M

题意：

对于一个长度为 $n$ 的序列 $a_i$，你可以进行若干次如下操作，使得最后其中所有数均相等：

选择一个长度为奇数的区间 $[l,r]$，令 $a_l\dots a_r$ 全部变为其中位数。

设一个序列的值可以通过这种操作使得最后剩的数的最大值。

求所有满足 $a_i\in[l_i,r_i]$ 的序列权值和。

多测，$1\leq T\leq 10$，$3\leq n\leq 150$，$1\leq l_i\leq r_i\leq 10^9$。

题解：

首先我们先分析对于一个固定的序列答案是什么，我们发现直接求值不容易，但判断答案是否比一个数大比较容易。

具体来说，我们可以规定答案最小为 $ans$，将序列中小于 $ans$ 的数赋为 0，大于等于 $ans$ 的数赋为 1，这样得到的序列如果能全变成 1，答案就大于等于 $ans$，否则答案小于 $ans$。

现在问题转化为 01 序列上操作，我们发现，如果存在两个 1 挨着，我们可以直接把左右全推成 1；如果有两个 1 只间隔一个 0，那么也可以操作这个 3-区间产生两个相邻的 1，然后就赢了；但如果任意两个 1 之间都距离两个 0 以上，那易得怎么操作都会劣，永远赢不了。这样我们就得到了判断一个序列答案是否大于等于某个数的充要条件。

对于本问题，考虑 DP，由于大于等于的状态不好设计，我们设 $f_{i,j,0/1/2}$ 表示考虑前 $i$ 位，答案小于 $j$，且上一个大于 $j$ 的位置在 $i$，$i-1$，$i-2$ 以前的情况数。写出 $j\in [l_i,r_i]$ 时的转移式 $f_{i,j,0}=(r_i-j+1)\times f_{i-1,j,2}$、$f_{i,j,1}=(j-l_i)\times f_{i-1,j,0}$ 和 $f_{i,j,2}=(j-l_1)\times (f_{i,j,1}+f_{i,j,2})$，而 $j\not\in[l_i,r_i]$ 时的转移是乘一个固定系数。

那我们发现，其实对于 $l_i$ 和 $r_i$ 分段后，每一段内的转移是大体类似的，如果看作是关于 $j$ 的多项式的话，我们发现转移是一模一样的，进而用上一道题的方式维护即可。

最后的答案可以写作 $\sum_{i} (f_{n,i+1,0}+f_{n,i+1,1}+f_{n,i+1,2}-f_{n,i,0}-f_{n,i,1}-f_{n,i,2})\times i$，这同样是一个关于 $i$ 的多项式，也可以通过插值求解，总次数最多 150 左右，可以取 155。