浅谈拉格朗日插值法

模板题链接：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;
}