前言
关于范德蒙德矩阵的傻逼证明自行百度。
点值表达
一个次数界为 \(n\) 的多项式 \(A(x)\) 的点值表达是一个由 \(n\) 个点对组成的集合:
\[\{(x_0,y_0),(x_1,y_1),\dots,(x_{n-2}, y_{n-2}),(x_{n-1},y_{n-1})\} \]其中 \(x_i\) 互不相同。
一个傻逼的性质， \(A(x) = B(x) + C(x)\) 时有：
\[A(x) = \{(x_0,By_0+Cy_0),(x_1,By_1+Cy_1),\dots,(x_{n-2},B y_{n-2}+C y_{n-2}),(x_{n-1},By_{n-1}+Cy_{n-1})\} \]\(A(x) = B(x) \times C(x)\) 时有：
\[A(x) = \{(x_0,By_0\times Cy_0),(x_1,By_1\times Cy_1),\dots,(x_{n-2},By_{n-2}\times C y_{n-2}),(x_{n-1},By_{n-1}\times Cy_{n-1})\} \]系数表达
一个次数界为 \(n\) 的多项式 \(A(x)\) 的系数表达是一个由 \(n\) 个系数组成的多项式:
\[a_0x^0 + a_1x^1 + a_2x^2 + \dots + a_{n-2}x^{n-2}+a_{n-1}x^{n-1} \]系数表达与点值表达的关系
对于任意一个由 \(n\) 个点对组成的点值表达都有唯一一个次数界为 \(n\) 的多项式与其对应。
有 \(y_i = A(x_i)\)。
把其写成矩阵形式：
\( \begin{bmatrix} 1 \quad x_0 \quad x_0^2 \quad &\cdots \quad x_0^{n-1}\\1 \quad x_1 \quad x_1^2 \quad &\cdots \quad x_1^{n-1}\\\vdots\quad\vdots\quad\vdots\quad&\ddots\quad\vdots\\1 \quad x_{n-1} \quad x_{n-1}^2 \quad &\cdots \quad x_{n-1}^{n-1}\\\end{bmatrix}\) \(\begin{bmatrix}a_0\\a_1\\\vdots\\a_{n-1}\end{bmatrix}\) \(=\) \(\begin{bmatrix}y_0\\y_1\\\vdots\\y_{n-1}\end{bmatrix}\)
范德蒙德矩阵在 \(x_i\) 皆不同的情况下有逆矩阵，因此有点值表达，能够确定系数 \(a_i\)。
拉格朗日插值
有：
\[A(x) = \sum_{i = 0}^{n-1} y_i\prod_{j \ne i}\dfrac{x-x_j}{x_i-x_j} \]设
\[A(x) = \{(x_0,y_0),(x_1,y_1),\dots,(x_{n-2}, y_{n-2}),(x_{n-1},y_{n-1})\} \]构造 \(A_i(x)\) 多项式满足：
\[A(x) = \sum_{i = 1}^{n-1}A_i(x_i) \]有
\[A_i(x) = \{(x_0,0),(x_1,0),\dots,(x_i,y_i),\dots,(x_{n-2},0),(x_{n-1},0)\} \]\[A(x) = \sum_{i = 1}^{n-1}A_i(x_i) = \{(x_0,y_0),(x_1,y_1),\dots,(x_{n-2}, y_{n-2}),(x_{n-1},y_{n-1})\} \]\[A_i(x) = y_i \prod_{j\ne i}\dfrac{x-x_j}{x_i-x_j} \]当 \(x = x_i\) 时有 \(\prod_{j\ne i}\dfrac{x_i-x_j}{x_i-x_j} = 1\)，所以 \(A_i(x_i) = y_i\)
当 \(x \ne x_i\) 且 \(x = x_j\) 时有 \(x-x_j = 0\) 有 \(\dfrac{x_i-x_j}{x_i-x_j} = 0\) ，所以 \(A_i(x_i) = 0\)
因为 \(j \ne i\) 所以分母不会为零。
所以
\[A(x) = \sum_{i = 1}^{n-1}A_i(x_i)= \sum_{i = 0}^{n-1} y_i\prod_{j \ne i}\dfrac{x-x_j}{x_i-x_j} \]#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p = 998244353;
ll ksm(ll x, ll y){
ll cur = 1; x = (x + p) % p;
while(y){
if(y&1) cur = (cur*x)%p;
x = (x*x)%p, y >>= 1;
}
return cur;
}
const int N = 5e4;
ll n, k, x_i[N], y_i[N], i, j, t;
int main(){
scanf("%lld %lld", &n, &k);
for(i = 1; i <= n; i ++)
scanf("%lld %lld", &x_i[i], &y_i[i]);
ll ans = 0;
for(i = 1; i <= n; i ++){
t = y_i[i];
for(j = 1; j <= n; j ++) if(i != j){
t = (1ll * t * ((k - x_i[j] + p)%p) % p * 1ll * ksm(x_i[i] - x_i[j], p-2) % p) % p;
}
ans = (ans + t) % p;
}
printf("%lld\n", ans);
return 0;
}