【学习笔记】拉格朗日插值

用法：给定(n+1)个点((x_i,y_i)),求满足这些点的多项式(f(k))处的值。

第一种思路显然暴力高斯消元，复杂度(O(n^3))且带精度问题。

换一种思路，让我们来构造这个多项式。

拉格朗日插值公式：(f(x)=sum_{i=1}^ny_iprod_{j ot=i}frac{x-x_j}{x_i-x_j}.)

我们将(x_i)带入，发现每一项的分母都不是(0)，且只有第(i)项不是(0.)且分子与分母都约去，只剩下(1),乘以前面的(y_i)就是正确答案。

于是，我们暴力计算(f(k))即可。逆元留到最后算可以省去一个(log.)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
inline int add(int a,int y){return (a+y)%mod;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
int n,k,x[5000],y[5000],ans;
inline int qpow(int a,int b){
	int res=1;
	if(a<=0||b==1)return a;
	while(b){
		if(b&1)res=mul(res,a);
		a=mul(a,a);b>>=1;
	}
	return res;
}
signed main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i){scanf("%d%d",x+i,y+i);}
	for(int i=1;i<=n;++i){
		int res=y[i];
		int fm=1,fz=1;
		for(int j=1;j<=n;++j){
			if(j==i)continue;
			fz=mul(fz,(k-x[j]+mod)%mod);
			fm=mul(fm,(x[i]-x[j]+mod)%mod);
		}
		fm=qpow(fm,mod-2);
		res=mul(res,mul(fz,fm));
		ans=add(res,ans);
	}
	printf("%d
",ans);
	return 0;
}

模板题：(Link)