「学习笔记」拉格朗日插值

题目大意

「模板」拉格朗日插值（Luogu 4781）

给定平面上的 $n$ 个点 $(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)$，它们可以确定一个至多 $n - 1$ 次多项式。问这个多项式在 $k$ 点的取值$\bmod 998244353$ 的结果。

数据范围：$n \le 2000$。

思路分析

我们可以构造一个多项式 $f_i(k)$ 满足它在 $x_i$ 处为 $1$，但是在 $x_j (i \neq j)$ 处为 $0$：

$$f_i(k) = \prod_{i \neq j} \frac{k - x_j}{x_i - x_j}$$

于是题目中求的多项式 $f$ 就是：

$$\begin {align} f(k) &= \sum_{i} y_i \times f_i(k) \\ &= \sum_{i} y_i \prod_{i \neq j} \frac{k - x_j}{x_i - x_j}。 \end {align}$$

这个多项式可以 $O(n^2)$ 计算，于是我们已经可以解决这个问题了。

但是我们发现在有些题目中，我们是动态维护这个过程的。也就是说，每次在平面上增加一个点，平面上的点确定的多项式的次数就会增加 $1$，然后我们求出所有这些多项式在 $k$ 点的值。

这时我们直接暴力做就变成 $O(n^3)$ 的了，不够优秀。观察式子，我们可以发现：

$$\begin {align} f(k) &= \sum_{i} y_i \prod_{i \neq j} \frac{k - x_j}{x_i - x_j} \\ &= \left( \prod_{i} (k - x_j)\right) \times \sum_{i} \frac{y_i}{k - x_i} \prod_{i \neq j} \frac{1}{x_i - x_j} \end {align}$$

令 $g = \prod_{i} (k - x_j), t_i = \frac{y_i}{\prod_{i \neq j} x_i - x_j}$，那么:

$$f(k) = g \sum_{i} \frac{t_i}{k - x_i}$$

这样，我们只需要再加入一个点的同时维护 $g, t_i$ 即可。$g$ 可以 $O(1)$ 地维护，而对于 $t_i$，我们需要扫一遍所有点，还要求 $n$ 个数的逆元，直接暴力做是 $O(n \log n)$ 的。但是，我们使用线性求逆元的科技即可把这一步优化到 $O(n)$。总复杂度 $O(n^2)$。

代码实现

这里采用动态的插值方法。

#include <cstdio>