拉格朗日插值

拉格朗日插值是沟通多项式的系数形式与点值形式的重要公式。

事实上，$n$ 个点确定唯一的多项式，其最高项次数为 $n-1$。

一般形式

核心思想是利用点值的可加性。什么意思呢？

构造一个函数 $f(x)$ 经过 $P(x_1,y_1),\cdots P(x_n,y_n)$，设第 $i$ 个点在 $x$ 轴上的投影为 $P_i^{\prime}(x_i,0)$。考虑构造 $n$ 个函数，使得 $f_i(x)$ 的图像经过 $\begin{cases}P_j^{\prime}(x_j,0),(j\neq i)\\P_i(x_i,y_i)\end{cases}$，则 $f(x)=\sum_{i=1}^{n}f_i(x)$。

设 $f_i(x)=a\prod_{j\ne i}(x-x_j)$，然后将 $P_i$ 的坐标代入求出 $a=\cfrac{y_i}{\prod_{j\ne i}(x_i-x_j)}$，进而导出：

$$f(k)=\sum_{i=1}^n y_i\prod_{i\ne j}\frac{k-x_j}{x_i-x_j}$$

这就是拉格朗日插值表达式。

如果要求出系数，用 $O(n^2)$ 卷出 $F(x)=\prod_{i=1}^n (x-x_i)$，然后对于每个 $i$ 暴力将 $F$ 除掉 $x-x_i$ 算出 $\cfrac{F(x)}{x-x_i}$ 的各项系数，再乘 $\cfrac{y_i}{\prod_{j\ne i}{x_i-x_j}}$ 即可得到 $f_i$ 的各项系数，加起来即可。时间复杂度为 $O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <iostream>
#include <cstdio>

using namespace std;
const int MOD = 998244353;

int poww(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % MOD)
        if (b & 1) res = 1ll * res * a % MOD;
    return res;
}

int n, k;
int x[2005], y[2005];

int main(void) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d%d", x + i, y + i);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int s1 = y[i], s2 = 1;
        for (int j = 1; j <= n; ++j)
            if (i != j) s1 = 1ll * s1 * (k - x[j]) % MOD, s2 = 1ll * s2 * (x[i] - x[j]) % MOD;
        ans = (ans + 1ll * s1 * poww(s2, MOD - 2)) % MOD;
    }
    printf("%d\n", (ans % MOD + MOD) % MOD);
    return 0;
}