2020-2021:teams:manespace:拉格朗日插值法
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:manespace:拉格朗日插值法 [2020/05/15 18:35] quantumbolt |
2020-2021:teams:manespace:拉格朗日插值法 [2020/05/15 19:04] (当前版本) quantumbolt |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| =====拉格朗日插值===== | =====拉格朗日插值===== | ||
| - | =====简介===== | + | ====简介==== |
| 行 7: | 行 7: | ||
| - | =====拉格朗日插值法===== | + | ====拉格朗日插值法==== |
| 众所周知， $n + 1$ 个 $x$ 坐标不同的点可以确定唯一的最高为 $n$ 次的多项式。在算法竞赛中，我们常常会碰到一类题目，题目中直接或间接的给出了 $n+1$ 个点，让我们求由这些点构成的多项式在某一位置的取值 | 众所周知， $n + 1$ 个 $x$ 坐标不同的点可以确定唯一的最高为 $n$ 次的多项式。在算法竞赛中，我们常常会碰到一类题目，题目中直接或间接的给出了 $n+1$ 个点，让我们求由这些点构成的多项式在某一位置的取值 | ||
| 行 88: | 行 88: | ||
| https://www.luogu.com.cn/blog/attack/solution-p4781 | https://www.luogu.com.cn/blog/attack/solution-p4781 | ||
| - | 下面是例题 | + | ==== 下面是例题 ==== |
| - | [[例题1 (洛谷P4781)]] | + | |
| - | [[例题2]] | + | |
| - | [[例题3]] | + | |
| - | https://www.luogu.com.cn/problem/P4781 | + | |
| - | ===== 题目背景 ===== | + | |
| - | + | ||
| - | 这是一道模板题 | + | |
| - | + | ||
| - | ===== 题目描述 ===== | + | |
| - | + | ||
| - | <del>由小学知识可知</del> $n$ 个点 $(x_i,y_i)$ 可以唯一地确定一个多项式 $y = f(x)$。 | + | |
| - | + | ||
| - | 现在，给定这 $n$ 个点，请你确定这个多项式，并求出 $f(k) \bmod 998244353$ 的值 | + | |
| - | + | ||
| - | ===== 输入格式 ===== | + | |
| - | + | ||
| - | 第一行两个整数 $n,k$。 | + | |
| - | + | ||
| - | 接下来 $n$ 行，第 $i$ 行两个整数 $x_i,y_i$。 | + | |
| - | + | ||
| - | ===== 输出格式 ===== | + | |
| - | + | ||
| - | 一行一个整数，表示 $f(k) \bmod 998244353$ 的值。 | + | |
| - | + | ||
| - | ===== 输入输出样例 ===== | + | |
| - | + | ||
| - | **输入 #1** | + | |
| - | + | ||
| - | <code> | + | |
| - | 3 100 | + | |
| - | 1 4 | + | |
| - | 2 9 | + | |
| - | 3 16 | + | |
| - | </code> | + | |
| - | **输出 #1** | + | |
| - | + | ||
| - | <code> | + | |
| - | 10201 | + | |
| - | </code> | + | |
| - | **输入 #2** | + | |
| - | + | ||
| - | <code> | + | |
| - | 3 100 | + | |
| - | 1 1 | + | |
| - | 2 2 | + | |
| - | 3 3 | + | |
| - | </code> | + | |
| - | **输出 #2** | + | |
| - | + | ||
| - | <code> | + | |
| - | 100 | + | |
| - | </code> | + | |
| - | ===== 说明/提示 ===== | + | |
| - | + | ||
| - | 样例一中的多项式为 $f(x)=x^2+2x+1$，$f(100) = 10201$。 | + | |
| - | + | ||
| - | 样例二中的多项式为 $f(x)=x$，$f(100) = 100$。 | + | |
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | $1 \le n \leq 2\times 10^3$，$1\le$ $x$<html><sub></html>i<html></sub></html>,$y$<html><sub></html>i<html></sub></html>,$k$ < $998244353$，$x_i$ 两两不同 | + | |
| - | ---- | + | |
| - | ===题解=== | + | |
| - | 拉格朗日插值的公式大概是 $f(k) = \sum_{i=0}^{n}y_i \prod_{j\neq i} \frac{k x_j}{x_i x_j}$ $x_i,y_i$ 是在 $x_i$ 的取值。 | + | |
| - | <code cpp> | + | |
| - | #include <bits/stdc++.h> | + | |
| - | #define int long long | + | |
| - | using namespace std; | + | |
| - | struct io { | + | |
| - | char buf[1 << 26 | 3], *s; int f; | + | |
| - | io() { f = 0, buf[fread(s = buf, 1, 1 << 26, stdin)] = '\n'; } | + | |
| - | io& operator >> (int&x) { | + | |
| - | for(x = f = 0; !isdigit(*s); ++s) f |= *s == '-'; | + | |
| - | while(isdigit(*s)) x = x * 10 + (*s++ ^ 48); | + | |
| - | return x = f ? -x : x, *this; | + | |
| - | } | + | |
| - | }; | + | |
| - | + | ||
| - | const int mod = 998244353; | + | |
| - | int qpow(int x, int y) { | + | |
| - | int res = 1; | + | |
| - | for(; y; y >>= 1, x = x * x % mod) | + | |
| - | if(y & 1) res = res * x % mod; | + | |
| - | return res; | + | |
| - | } | + | |
| - | int inv(int x) { return qpow(x, mod - 2); } | + | |
| - | + | ||
| - | int n, k; | + | |
| - | const int maxn = 2e3 + 32; | + | |
| - | int x[maxn], y[maxn]; | + | |
| - | + | ||
| - | #define out cout | + | |
| - | signed main() { | + | |
| - | #ifdef LOCAL | + | |
| - | #define in cin | + | |
| - | ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); | + | |
| - | freopen("testdata.in", "r", stdin); | + | |
| - | #else | + | |
| - | io in; | + | |
| - | #endif | + | |
| - | in >> n >> k; | + | |
| - | for(int i = 1 ; i <= n ; i ++) in >> x[i] >> y[i]; | + | |
| - | int ans = 0; | + | |
| - | for(int i = 1 ; i <= n ; i ++) { | + | |
| - | int a, b; a = b = 1; | + | |
| - | for(int j = 1 ; j <= n ; j ++) if(i ^ j) { a = a * (k - x[j]) % mod; } | + | |
| - | for(int j = 1 ; j <= n ; j ++) if(i ^ j) { b = b * (x[i] - x[j]) % mod; } | + | |
| - | a = (a + mod) % mod, b = (b + mod) % mod, b = inv(b); | + | |
| - | ans = (ans + a * b % mod * y[i] % mod) % mod; | + | |
| - | } | + | |
| - | out << ans << '\n'; | + | |
| - | return 0; | + | |
| - | } | + | |
| - | </code> | + | |
| + | * [[洛谷P4781]] https://www.luogu.com.cn/problem/P4781 | ||
| + | * 洛谷P4593 https://www.luogu.com.cn/problem/P4593 | ||
2020-2021/teams/manespace/拉格朗日插值法.1589538933.txt.gz · 最后更改: 2020/05/15 18:35 由 quantumbolt
