【小记】拉格朗日插值
拉格朗日插值是知道\(n\)次多项式在\(n+1\)个点的点值，快速求出\(f(x')\)的算法
结论
拉格朗日插值本质上就是该式子，首先我们知道的点值为当\(x=x_i\)时\(f(x)=y_i\)
\[f(x)=\sum_{i=0}^{n}y_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}
\]
推导
首先假设我们考虑第\(i\)个点值。
那么我们先将另外\(n\)个点值，映射到\(x\)轴上。
即我们考虑构造函数\(g_i(x)\)当\(\forall j\ne i\)时\(g_i(x_j)=0\)，且\(g_i(x_i)=y_i\)
那么显然的\(f(x)=\sum_{i=0}^{n}g_i(x)\)
并且可以发现
\[g_i(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}
\]
是满足条件的构造
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=998244353;
LL fpow(LL a,LL b){LL ret=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1)ret=ret*a%mod;
return ret;
}
const int N=2e3+5;
LL X[N],Y[N];
int main(){
LL n,k,ans=0,now;
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d%d",&X[i],&Y[i]);
for(int i=1;i<=n;i++){
now=Y[i];
for(int j=1;j<=n;j++)if(i^j)
now=now*(k-X[j]+mod)%mod*fpow(X[i]-X[j]+mod,mod-2)%mod;
ans=(ans+now)%mod;
}
printf("%lld",ans);
return 0;
}