传送门
拉格朗日插值法
帅气的英文名:Lagrange………
看起来很厉害的名字是用来干什么的呢？
简单点说，就是给你n个点，你就可以确定一个n次多项式。
设这n个点分别为：
((x_1,y_1)(x_2,y_2)(x_3,y_3)cdotscdots(x_n,y_n))
则公式为：
[f(i)=sum_{i=1}^n y_iprod_{i
e j}frac{(k-x_j)}{x_i-x_j}
]
你把每个x带进去会巧妙的发现都成立。
然后对于求x=k时的值，只需把分子乘上分母的逆元即可。（因为模数是个大质数，所以可直接费马小定理）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=2005;
const int mod=998244353;
int n;
long long k,x[maxn],y[maxn],ans;
long long fastpower(long long a,long long b){
if(b==0) return 1;
if(b==1) return a%mod;
long long res=fastpower(a,b/2);
if(b&1) return res*res%mod*a%mod;
return res*res%mod;
}
int main(){
scanf("%d%lld",&n,&k);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&x[i],&y[i]);
}
for(int i=1;i<=n;i++){
long long nx=y[i],ny=1;
for(int j=1;j<=n;j++){
if(i==j) continue;
nx=nx*(k-x[j])%mod;
ny=ny*(x[i]-x[j])%mod;
}
nx=nx*fastpower(ny,mod-2)%mod;
ans=(ans+nx)%mod;
}
printf("%lld",(ans+mod)%mod);
return 0;
}