学习笔记 - 拉格朗日插值 | Lucky_Glass's Blog
0%

学习笔记 - 拉格朗日插值

我猜我只学习了比较简单的一部分……


# 插值法

根据多项式函数的基本知识,我们知道平面上任意横坐标不同的 $n$ 个点,可以确定一个次数为 $n-1$ 的函数曲线。

插值法则是在给定这 $n$ 个点的情况下计算函数曲线的表达式。

这一点类似于拟合,只不过插值要求经过每一个点,而拟合只需要使每个点大致趋近于曲线即可。

拉格朗日插值法是众多插值法中比较简单的一个。


# 算法内容

记给出的点为 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$,要计算出一个次数为 $n-1$(项数为 $n$)的一个函数 $F(x)$。

拉格朗日插值法的原理是:把 $F(x)$ 表示成 $n$ 个易于计算的曲线之和,即

于是可以这样构造 $F_i(x)$ —— $F_i(x)$ 在 $x_i$ 处取值为 $y_i$,在 $x_j$($j\neq i$)处取值为 $0$,根据这个思路构造出的 $F_i(x)$ 如下:

易于证明上式在 $x_i$ 处取 $y_i$,在 $x_j$($j\neq i$)处取 $0$。


# 模板

> 洛谷 P4781

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2e3+10,MOD=998244353;

inline int Add(const int &a,const int &b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(const int &a,const int &b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(const int &a,const int &b){return 1ll*a*b%MOD;}
inline int Model(const int &a){return (a%MOD+MOD)%MOD;}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a),b>>=1;}return r;}

int n,m;
int pnt[N][2];

int Poly(int x){
int ret=0;
for(int i=1;i<=n;i++){
int ovr=Model(pnt[i][1]),blw=1;
for(int j=1;j<=n;j++)
if(j!=i){
ovr=Mul(ovr,Sub(x,pnt[j][0]));
blw=Mul(blw,Sub(pnt[i][0],pnt[j][0]));
}
ret=Add(ret,Mul(ovr,Pow(blw,MOD-2)));
}
return ret;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d",&pnt[i][0],&pnt[i][1]);
printf("%d\n",Poly(m));
return 0;
}

# 优化DP

这样一个计算多项式的算法如何优化DP?

实际上,这要求DP值的计算方式是一个多项式。当我们代入该多项式的自变量非常的大时,我们不能直接去DP计算这个值;但是如果我们可以证明这个多项式的次数比较小(比如为 $n$),就能够只计算出在这个多项式中的 $n$ 个点($n$ 个DP值),再用拉格朗日插值法求出多项式,代入自变量求解即可。

- 【例题】calc「集训队互测」

> 洛谷 P4463

解析

因为是要选出 $n$ 个不同的数,我们就可以先不考虑这些数的顺序,只是选出这些数再全排一下就好了。

先写出一个非常暴力的DP,即 $f_{i,j}$ 表示在 $[1,j]$ 的数中选了 $i$ 个数,这些数的积之和:

然后我们假设当 $i$ 固定时 $f_{i,j}$ 是一个关于 $j$ 的多项式 $F_i(j)$,考虑利用数学归纳法证明:

  • 当 $i=0$ 时,$F_i(j)$ 是常数多项式;
  • 当 $i>0$ 时,由递推式可得,因多项式的和、积均为多项式,所以 $F_i(j)$ 为多项式。

> Hint. 若 $F(x)$ 是一个 $n$ 次多项式,则 $F(x)-F(x-1)$ 是一个 $n-1$ 次多项式。

再计算 $F_i(j)$ 的次数,设为 $h(i)$。根据递推式,可得

而 $h(0)=0$,则 $h(n)=2n$。也即 $F_n(j)$ 是一个 $2n$ 次多项式,需要确定 $2n+1$ 个点。于是只需要算出 $f_{i,k}$($k\in[1,2n+1]$)就可以得到 $F_n(j)$,最后把 $j=k$ 代入就可以得到答案了。


THE END

Thanks for reading!