专栏文章

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

BBlackHoles
P4781题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mio7msz6
此快照首次捕获于
2025/12/02 14:41
3 个月前
此快照最后确认于
2025/12/02 14:41
3 个月前
查看原文

前置知识

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

正解：拉格朗日插值法

首先，对于一个 n−1n - 1 次多项式 y=f(x)y = f(x)，给定 nn 个横坐标两两不同的点，可以唯一确定这个函数，题目便需要我们求出单点值。
我们考虑对于 1≤i≤n1 \le i \le n，都构造一个函数 fi(x)f_i(x) 使得当且仅当 x=xix = x_i 时，函数值为 11，否则为 00。这样的话，函数 gi(x)=yi×fi(x)g_i(x) = y_i \times f_i(x) 当且仅当 x=xix = x_i 时为 yiy_i，否则为 00。
这样的话，原函数 F(x)=∑i=1ngi(x)F(x) = \sum_{i = 1}^n g_i(x)。
那么问题就变成了构造函数 fi(x)f_i(x)。我们观察这个函数：Gi(x)=∏j≠i(x−xj)G_i(x) = \prod_{j \ne i} (x - x_j)，发现当 j≠ij \ne i 时，Gi(xj)=0G_i(x_j) = 0。于是 fi(x)f_i(x) 便容易构造了：fi(x)=∏j≠i(x−xjxi−xj)f_i(x) = \prod_{j \ne i} (\frac{x - x_j}{x_i - x_j})。求和的时候记录分子积与分母积，最后求分母逆元即可。

Code

CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...