插值

参考资料

• 插值 - OI Wiki

拉格朗日插值

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

$$f(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 【模板】拉格朗日插值

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