浅谈拉格朗日插值法

模板题链接：P4781 【模板】拉格朗日插值

题意：

给定 \(n\) 个点 \(P_i(x_i,y_i)\) ，将过该 \(n\) 个点的最多 \(n-1\) 次多项式记为 \(f(x)\)

给出 \(k\) ，求 \(f(k) \bmod 998244353\)

\[ f(k) = \sum\limits_{i=1}^{n}y_i\prod_{j\ne i}{ \dfrac{k-x_j}{x_i-x_j} } \]

证明：过 \(P_i\) 作垂线交 \(x\) 轴于 \(H_i(x_i,0)\)

构造 \(g_i(x),i=1,2,\cdots ,n\) ，使得 \(g_i(x)\) 的图像过 \(\begin{cases}P_i(x_i,y_i) \\[8pt] H_j(x_j,0),j\ne i\end{cases}\)

可以发现，\(g_i(x) = a \prod_{j\ne i}{(x-x_j)}\) ，其中 \(a\) 是未知数

因为 \(g_i(x)\) 过 \(P_i(x_i,y_i)\) ，代入并整理可得

\[ a = \dfrac{y_i}{ \prod_{j\ne i}{(x_i-x_j)} } \] 把 \(a\) 代入 \(g_i(x)\) 得 \[ g_i(x) = y_i\times\dfrac{ \prod_{j\ne i}{(x-x_j)} }{ \prod_{j\ne i}{(x_i-x_j)} } = y_i\prod_{j\ne i}\dfrac{x-x_j}{x_i-x_j} \] 故 \[ f(x) = \sum\limits_{i=1}^{n}g_i(x) = \sum\limits_{i=1}^{n}y_i\prod_{j\ne i}\dfrac{x-x_j}{x_i-x_j} \]

把 \(k\) 代入即可得

\[ f(k) = \sum\limits_{i=1}^{n}y_i\prod_{j\ne i}{ \dfrac{k-x_j}{x_i-x_j}} \]

求解时可以先分别求出分子和分母，最后分子乘上分母的逆元即可

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
#define pc(a) putchar(a)
#define mod (int)(998244353)
template<typename T>inline void read(T &k)
{
	char ch=gc();T x=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
	k=x*f;
}
template<typename T>inline void write(T k)
{
	if(k<0){k=-k;pc('-');}
	if(k>9)write(k/10);
	pc(k%10+'0');
}
#define MAXN (int)(2e3+5)
int qpow(int a,int b)
{
	int ans=1,base=a;
	while(b)
	{
		if(b&1)ans=ans*base%mod;
		base=base*base%mod;
		b>>=1;
	}
	return ans;
}
int inv(int x){return qpow(x,mod-2);}
int n,k,a,b,ans;
int x[MAXN],y[MAXN];
signed main()
{
	read(n);read(k);
	for(int i=1; i<=n; i++)
		read(x[i]),read(y[i]);
	for(int i=1; i<=n; i++)
	{
		a=y[i]%mod,b=1;
		for(int j=1; j<=n; j++) if(i!=j)
		{
			b=(x[i]-x[j]+mod)%mod*b%mod;
			a=(k-x[j]+mod)%mod*a%mod;
		}
		ans=(ans+a*inv(b)%mod)%mod;
	}
	write(ans);pc('\n');
	return 0;
}