0. 基础知识：
关于多项式的定义：
-
多项式：一个形如 \(f(x) = \sum_{i = 0} ^n a_i x^i\) 的有限和式被称为多项式。
-
系数：多项式第 \(i\) 项的系数在上面就表示为 \(a_i\)。
-
度（次数）：多项式中最高次数的项的次数就被称为该多项式的度，也称次数。
多项式表示法：
多项式有两种表示法：分别是 系数表示法 和 点值表示法。其中系数表示法就形如上面给出的形式。
而点值表示法则是用不同的 \(n + 1\) 个点来表示一个 \(n\) 次多项式。其中 两点确定一条直线 就是一个很好的例子。如何快速的在两者中快速转化呢？这是我们要研究的问题。其中从点值表示法到系数表示法的过程叫插值，从系数表示法到点值表示法的过程叫求值。
1.拉格朗日插值：
接下来先研究一下如何快速插值。首先一个简单的想法是直接列出 \(n + 1\) 条方程式并使用高斯消元，但这样是 \(O(n^3)\) 的，能不能更快呢？
我们尝试换一种多项式的表现方式：考虑给每个 \(y_i\) 前面都加上一个系数 \(k_i\) 并求和，并当 \(x = x_i\) 时该 \(k_i\) 取到 \(1\)，对于其他的情况取到 \(0\)。但这样还是比较困难的，注意到我们只关心该多项式的表达式在这 \(n + 1\) 的表现，于是考虑将 \(k_i\) 的定义变为：当 \(x\) 为任意 \(x_j(j \ne i)\) 时，\(k_i\) 取到 \(0\)，其他情况取到 \(1\)。形式化的：令 \(f(x) = \sum_{i = 1} ^ {n + 1} k_iy_i\)，其中 \(k_i = [\forall j(1 \le j \le n + 1, j \ne i), x \ne x_j]\)。
于是我们只需要构造出合适的 \(k_i\) 满足上述条件即可，显然 \(\prod_{j \ne i} (x - x_j)\) 会在 \(x\) 取到任意 \(x_j, j \ne i\) 时取到 \(0\)，但是当 \(x = x_i\) 时，该式子不是 \(1\)，那就把多出来的除掉即可。于是得到 \(k_i = \prod_{j \ne i} \frac{x-x_j}{x_i-x_j}\)。于是 \(f(x) = \sum_{i = 1}^{n + 1}y_i \prod_{j \ne i} \frac{x-x_j}{x_i-x_j}\)。算法时间复杂度降到了 \(O(n^2)\)，这便是拉格朗日插值。
P4781 【模板】拉格朗日插值
qwq
#include<bits/stdc++.h>
#define int long long
#define inv(x) qpow(x, mod - 2)
using namespace std;
const int N = 2e3 + 10, mod = 998244353;
int n, k, ans;
struct point{
int x, y;
}p[N];
int qpow(int x, int y){
int ret = 1;
for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
return ret;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y;
for(int i = 1; i <= n; i++){
int sum1 = p[i].y, sum2 = 1;
for(int j = 1; j <= n; j++){
if(i == j) continue;
sum1 = (sum1 * ((k - p[j].x + mod)) % mod) % mod;
sum2 = (sum2 * ((p[i].x - p[j].x + mod) % mod)) % mod;
}
ans = (ans + sum1 * inv(sum2) % mod) % mod;
}
cout << ans;
// system("pause");
return 0;
}