今天 \(T2\) 用到了，于是来学一学。
拉格朗日插值法
求值是指给定一个函数式，根据一个自变量求出因变量。
而插值是给出一些自变量及其对应的因变量，求出符合的函数式。
一种方法是将所有的值代入，然后解方程，显然极其不方便，这时，一位名为约瑟夫·路易斯·拉格朗日的人站了出来，提出了拉格朗日插值法。
假设有一个函数，满足 \(g(x_i)=1\)，且 \(g(x_j)=0,(i\ne j)\)，那么显然所求多项式即为：
\[f(x)=\sum_{i=1}^{n}{y_i\times g_x}
\]
对于一个非 \(i\) 的 \(j\)，想要消除其影响就要使其系数为0，也就是说我们构造的函数需要有一项为 \((x-x_j)\)。
对于 \(i\)，想要其值为1，就得消掉其他项，所以需要除以 \((x_i-x_j)\)。
所以函数为：
\[g_x=y_i\times \prod_{i\ne j} \frac{x-x_j}{x_i-x_j}
\]
\[f_x=\sum_{i=1}^{n}{y_i\times \prod_{i\ne j} \frac{x-x_j}{x_i-x_j}}
\]
复杂度为 \(O(n^2)\)
code
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
const long long M=2e3+10;
long long n,k,ans;
long long x[M],y[M];
inline long long read(){
long long x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
inline long long po(long long x,long long k){
long long ans=1;
while(k){
if(k&1){
ans=ans*x%mod;
}
x=x*x%mod;
k=k>>1;
}
return ans;
}
int main(){
n=read(); k=read();
for(long long i=1;i<=n;i++){
x[i]=read(); y[i]=read()%mod;
}
for(long long i=1;i<=n;i++){
long long res=1,a=1,b=1;;
for(long long j=1;j<=n;j++){
if(i==j){
continue;
}
a=a*(k-x[j])%mod;
b=b*(x[i]-x[j])%mod;
}
if(b<0){
res=-res;
}
ans=(ans+res*y[i]%mod*a%mod*po(abs(b),mod-2)%mod)%mod;
}
cout<<(ans+mod)%mod<<'\n';
return 0;
}
对于一些自变量连续的点，我们可以将复杂度优化至 \(O(n)\)。
对于上面的函数，由于自变量连续，显然有：
\[g_x=y_i\times \prod_{i\ne j} \frac{x-j}{i-j}
\]
\[g_x=y_i\times \frac{\prod_{i\ne j}{x-j}}{\prod_{i\ne j}{i-j}}
\]
\[\prod_{i\ne j}{x-j}=\frac{\prod_{i=1}^{n}{x-j}}{x-i}
\]
\[\prod_{i\ne j}{i-j}=(-1)^{n-i}\times (i-1)! \times (n-i)!
\]
\[g_x=\frac{\prod_{i=1}^{n}{x-j}}{(x-i)\times (-1)^{n-i}\times (i-1)! \times (n-i)!}
\]
\[f_x=\sum_{i=1}^{n}{y_i\times \frac{\prod_{i=1}^{n}{x-j}}{(x-i)\times (-1)^{n-i}\times (i-1)! \times (n-i)!}}
\]
复杂度为 \(O(n)\)。