题解：P4781 【模板】拉格朗日插值

· · 题解

前置知识

此题为模板题，仅需要逆元与基本数学函数知识。

正解：拉格朗日插值法

首先，对于一个 n - 1 次多项式 y = f(x)，给定 n 个横坐标两两不同的点，可以唯一确定这个函数，题目便需要我们求出单点值。

我们考虑对于 1 \le i \le n，都构造一个函数 f_i(x) 使得当且仅当 x = x_i 时，函数值为 1，否则为 0。这样的话，函数 g_i(x) = y_i \times f_i(x) 当且仅当 x = x_i 时为 y_i，否则为 0。

这样的话，原函数 F(x) = \sum_{i = 1}^n g_i(x)。

那么问题就变成了构造函数 f_i(x)。我们观察这个函数：G_i(x) = \prod_{j \ne i} (x - x_j)，发现当 j \ne i 时，G_i(x_j) = 0。于是 f_i(x) 便容易构造了：f_i(x) = \prod_{j \ne i} (\frac{x - x_j}{x_i - x_j})。求和的时候记录分子积与分母积，最后求分母逆元即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll Mod = 998244353;
const int N = 2005;
int n;
ll x[N], y[N], k;
ll ans;
ll qpow(ll base, int power) {
    ll res = 1;
    while (power) {
        if (power & 1) res = res * base % Mod;
        base = base * base % Mod;
        power >>= 1;
    }
    return res;
}
int main(void) {
    cin.tie(0) -> ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> x[i] >> y[i];
    for (int i = 1; i <= n; ++i) {
        ll p = 1, q = 1;
        for (int j = 1; j <= n; ++j)
            if (j != i)
                p = p * ((k - x[j] + Mod) % Mod) % Mod, q = q * ((x[i] - x[j] + Mod) % Mod) % Mod;
        ans = (ans + p * qpow(q, Mod - 2) % Mod * y[i] % Mod) % Mod;
    }
    cout << ans;
    return 0;
}