Skip to main content

插值

Summary

拉格朗日插值由 n 个横坐标互不相同的点唯一确定一个次数不超过 n-1 的多项式。做法是为每个点构造一个在自身处取 1、在其余点处取 0 的基函数，乘以该点纵坐标后求和，即得经过全部点的插值多项式，可直接代入求任意单点的取值。给出插值公式与模意义下的实现，其中除法通过快速幂求逆元完成，求单点值的时间复杂度为 O(n^2)。配套例题为洛谷 P4781。

参考资料​

拉格朗日插值​

由 nn 个横坐标互不相同的点 (xi,yi)(x_i,y_i) 可唯一确定一个不超过 n−1n-1 次的多项式 ff。拉格朗日插值为每个点构造一个在 xix_i 处取 11、在其余 xjx_j 处取 00 的基函数，乘以 yiy_i 后求和即得 ff，可直接代入求任意点的值。求单点值的时间复杂度为 O(n2)O(n^2)。

f(x)=∑i=1nyi⋅∏j≠ix−xjxi−xjf(x)=\sum_{i=1}^ny_i\cdot\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}
250 Bcpp
ll lagrange(int n,int k)
{
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		ll p=1,q=1;
		for(int j=1;j<=n;j++)
		{
			if(i==j)continue;
			p=p*(k-x[j])%mod;
			q=q*(x[i]-x[j])%mod;
		}
		ans=(ans+y[i]*(p*Pow(q,mod-2)%mod)%mod)%mod;
	}
	return (ans+mod)%mod;
}

例题​

洛谷 P4781 【模板】拉格朗日插值

给定 nn 个点，请你确定这个多项式，并求出 f(k) mod 998244353f(k)\bmod 998244353 的值。