没进水的脑子


——博客——

拉格朗日插值证明+模板

  • ~2.69K 字
  1. 1. 拉格朗日插值
    1. 1.1. 定义
      1. 1.1.1. 概念
      2. 1.1.2. 定理
        1. 1.1.2.1. 证明
    2. 1.2. 模板
  • 开学力，悲（虽然一直没放假吧）。在做往年 真题的时候出现了这么一道题，于是开始恶补拉格朗日插值（之前学的都还给高数课本了）。

拉格朗日插值

首先让我们一起膜拜一下约瑟夫·拉格朗日。

定义

概念

一般地，若已知 在互不相同 个点 处的函数值 （即该函数过 这 个点），则可以考虑构造一个过这 个点的、次数不超过 的多项式 ,使其满足：

要估计任一点 ，，则可以用 的值作为准确值 的近似值，此方法叫做“插值法”。
称上述式为插值条件（准则），含 的最小区间 ，其中 。

定理

满足插值条件的、次数不超过 的多项式是存在而且是唯一的。

证明

我们先回顾一下当 的情况，也就是小升初就学过的“待定系数法”。

给定两个点 和 ，求出函数 的表达式。

这个大家都会，我就不赘述了，下面我们换一个问法，求出函数 的值 （ 为给定实数）。下面我们用给定的两个点表示一下该值。

接下来我们引入一个叫做线性插值基函数的东西，其表示为 ，意义为 。

因此

接着，我们来考虑考虑 的情况。

易得

接下来我们考虑一般情况。

已知函数 在 个插值节点 上的函数值为 ，求构造一个次数不超过 的插值函数多项式 ，使得 成立。

由此可得

至此我们就获得了拉格朗日插值公式

模板

根据公式，我们可以直接写出 算法：

Code(mod=998244353)
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
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int N = 2010;
int n, k;
int x[N], y[N];
int qpow(int x, int y) {
    x %= mod;
    int ans = 1;
    while (y) {
        if (y & 1) ans = (ans * x) % mod;
        y >>= 1;
        x = (x * x) % mod;
    }
    return ans;
}
int inv(int x) {
    return qpow(x, mod - 2);
}
signed main() {
    cin >> n >> k;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    for (int i = 1; i <= n; i++) {
        int mum = 1;
        int son = y[i];
        for (int j = 1; j <= n; j++) {
            if (j == i) continue;
            son = son * (k - x[j]) % mod;
            mum = mum * ((x[i] - x[j] % mod) % mod) % mod;
        }
        ans += son * inv(mum) % mod;
        ans = (ans + mod) % mod;
    }
    cout << ans;
}