拉格朗日插值学习笔记
概念
拉格朗日插值用于拟合一个函数。可以通过已知函数中的点拟合出函数。若为 \(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)}\)。带入原函数则为
\[f_i(x)=\prod\limits_{j=1,i\neq j}^{n+1}(x-X_j)*\frac{Y_i}{\prod\limits_{j=1,i\neq j}^{n+1}(X_i-X_j)} \]一般写成
\[f_i(x)=Y_i*\prod\limits_{j=1,i\neq j}^{n+1}\frac{(x-X_j)}{(X_i-X_j)} \]则最终函数为
\[F(x)=\sum\limits_{i=1}^{n} f_i(x) \]\[F(x)=\sum\limits_{i=1}^{n} Y_i*\prod\limits_{j=1,i\neq j}^{n+1}\frac{(x-X_j)}{(X_i-X_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);
}