拉格朗日插值學習筆記

概念

拉格朗日插值用于擬合一個函數?？梢酝ㄟ^已知函數中的點擬合出函數。若為 \(n\) 次函數，則需要多于 \(n+1\) 個點。

做法

考慮構造 \(n+1\) 個函數，第 \(i\) 個函數 \(f_i\) 對應點 \(i\) 滿足 \(f_i(X_i)=Y_i\) 且對于其他的點 \(j(i\neq j)\) 滿足 \(f_i(X_j)=0\)。顯然最后結果就為 \(\sum\limits_{i=1}^{n+1} f_i\)。

滿足后者，我們只需要讓函數 \(f_i\) 形如 \(\prod\limits_{j=1}^{n+1}(x-X_j)(i\neq j)\) 即可?？紤]滿足后者。

因為 \(0\) 的倍數為 \(0\)，所以給函數加系數不影響。當前函數 \(f_i\) 取 \(X_i\) 時為 \(\prod\limits_{j=1}^{n+1}(X_i-X_j)(i\neq j)\) 則讓當前值變為 \(Y_i\) 可以乘 \(\frac{Y_i}{\prod\limits_{j=1}^{n+1}(X_i-X_j)(i\neq j)}\)。帶入原函數則為

一般寫成

則最終函數為

代碼（模板拉格朗日插值）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#define mod 998244353
#define int long long
using namespace std;
int n,k;
int x[100001],y[100001],ans;
int pow(int a,int b)
{
	int re=1;
	while(b)
	{
		if(b&1)
		{
			re*=a;
			re%=mod;
		}
		a*=a;
		a%=mod;
		b>>=1;
	}
	return re;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x[i],&y[i]);
		x[i]%=mod;
		y[i]%=mod;
	}
	for(int i=1;i<=n;i++)
	{
		int mul=1,mul2=1;
		for(int z=1;z<=n;z++)
		{
			if(i==z) continue;
			mul*=(k-x[z])%mod;
			mul2*=(x[i]-x[z])%mod;
			mul%=mod;
			mul2%=mod;
		}
		ans+=mul*pow(mul2,mod-2)%mod*y[i]%mod;
		ans%=mod;
	}
	printf("%lld",(ans%mod+mod)%mod);
}