拉格朗日插值(洛谷4781)

给你平面上的 n 个点,可以唯一确定一个多项式。

现在告诉你这些点的坐标和 k ,请你求出多项式在 k 的取值。

思路

显然我们可以根据题意列出 n 个方程,利用高斯消元求解后带入。时间复杂度O(n ^ 3)

我们可以利用插值法求解并使得时间复杂度降至O(n ^ 2)

拉格朗日插值

拉格朗日基本多项式为:

1533897851850.png

对于这个多项式,他有一个神奇的性质,如果你带入 x[j],可以获得 1 (分子分母相同);如果带入 x[i],可以获得 0 (其中必有一项的分子值为 0 )。由此,我们可以列出这个 n 次多项式。

1533899066409.png

由于某些前面所述的基本多项式的性质,带入 x[i] 可以获得 y[i] ,即该函数的图像经过题目所要求的 n 个点。可以经过严格的数学证明(知乎上有)可以证明这个多项式即所求的。

然鹅我们并不需要了解那么多,既然这个多项式就是所求多项式,我们带进去用就可以了。另外,由于其中涉及到除法和取模,我们可以考虑乘法逆元。同时,我们可以每次处理出分子和分母再求逆元(而不是实时求逆元),即可保证时间复杂度为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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 2010, Mod = 998244353;
int n, k;
ll s1, s2, ans;
ll x[maxn], y[maxn];

ll inv(ll x) {
if (x == 0 || x == 1) return 1;
if (x < 0) return inv((x % Mod + Mod) % Mod);
return (Mod - Mod / x) * inv(Mod % x) % Mod;
}

int main() {

n = read(), k = read();
for (int i = 1; i <= n; i++)
x[i] = read(), y[i] = read();

for (int i = 1; i <= n; i++) {
s1 = s2 = 1;
for (int j = 1; j <= n; j++)
if (i != j) {
s1 = s1 * (k - x[j]) % Mod;
s2 = s2 * (x[i] - x[j]) % Mod;
}
ans = (ans + s1 * inv(s2) % Mod * y[i] % Mod + Mod) % Mod;
}
printf("%lld\n", ans);

return 0;
}

参考资料

题目链接:

参考资料:

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×