Introduce
给定 \(n\) 个点，那么可以确定一个不超过 \(n-1\) 项的多项式函数值。我们可以使用高斯消元，但是 \(O(n^3)\) 的时间复杂度和精度误差难以接受。
Principle
我们考虑构造函数 \(fi\) ，满足其在 \(x=x_i\) 时函数值为 \(1\) ，在 \(x=x_j(j\neq i,j\in[1,n])\) 是 \(0\)，这很好构造： $fi(x)=\prod_{j\neq i}\frac{x-x_j}{x_i-x_j} $ 。
然后再构造 \(f(x)=\sum_{i=1}^{n}y_ifi(x)\) ，那么这个函数就经过这 \(n\) 个点。
\(f(x)=\sum_{i=1}^{n}y_i\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}\)
\(\text{P4781 【模板】拉格朗日插值}\)
给定 \(n\) 点确定多项式，求 \(f(k)\) ，直接代入上面的公式。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+110,mod=998244353;
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
int n,k,x[N],y[N],ans;
int ksm(int x,int y){
int sum=1;
while(y){
if(y&1)sum=(sum*x)%mod;
y>>=1;
x=(x*x)%mod;
}
return sum%mod;
}
signed 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++){
int tmp=y[i];
for(int j=1;j<=n;j++)if(j!=i)tmp=tmp%mod*(k-x[j])%mod*ksm(x[i]-x[j],mod-2)%mod;
ans=(ans+tmp)%mod;
}
printf("%lld\n",(ans+mod)%mod);
return 0;
}