拉格朗日插值的应用
程序员文章站
2022-06-07 09:59:14
...
引言:
什么是拉格朗日插值?假设我们现在有三个点 ,现在我们要找一条唯一的二次曲线刚好经过这三个点。
拉格朗日给出了一个绝妙的方法,他把我们要求的曲线的表达式等同于三个函数的累加。具体是这么操作的:
第一个函数保证
第二个函数保证
第三个函数保证
那么我们所要求的函数即为:
可以保证的是这个函数同时经过并且是唯一的满足条件的二次函数。
公式:
如果上面的部分你看懂了,那么你已经掌握了拉格朗日插值的用法和思想。接下来我们要做的就是寻找一个公式使得利用现在已有的个点,来推导出次的函数。
那么这个函数为:
实现:
一般情况下拉格朗日插值的复杂度是,即:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
typedef long long ll;
const ll mod = 998244353;
struct point{
ll x,y;
}p[N];
int n,k;
ll qpow(ll a,ll b,ll mod){
ll ans=1;
while(b){
if(b&1){
ans=(ans%mod*a%mod)%mod;
}
a=(a%mod*a%mod)%mod;
b>>=1;
}
return ans%mod;
}
ll Lagrange(int k){
ll ans=0;
for(int j=1;j<=n;j++){//
ll base1=1;
ll base2=1;
for(int i=1;i<=n;i++){//lj(k)基函数
if(j==i) continue;
base1=(base1%mod*((k-p[i].x)%mod+mod)%mod)%mod;
base2=(base2%mod*((p[j].x-p[i].x)%mod+mod)%mod)%mod;
}
ans=(ans%mod+(p[j].y%mod*base1%mod*qpow(base2,mod-2,mod)%mod)%mod)%mod;
}
return ans;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
cout<<Lagrange(k)<<endl;
return 0;
}
如果已知的坐标是连续的话,那么我们可以通过预处理使得复杂度变为,代码以codeforces 622F为例。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
typedef long long ll;
const ll mod = 1e9+7;
ll p[N],x[N],s1[N],s2[N],ifac[N];
ll qpow(ll a,ll b){
ll ans=1;
while(b){
if(b&1) ans=(ans%mod*a%mod)%mod;
a=(a%mod*a%mod)%mod;
b>>=1;
}
return (ans%mod+mod)%mod;
}
//拉格朗日插值,n项,每个点的坐标为(x_i,y_i),求第xi项的值,保证x是连续的一段
ll lagrange(ll n, ll *x, ll *y, ll xi) {
ll ans = 0;
s1[0] = (xi-x[0])%mod, s2[n+1] = 1;
for (ll i = 1; i <= n; i++) s1[i] = 1ll*s1[i-1]*(xi-x[i])%mod;
for (ll i = n; i >= 0; i--) s2[i] = 1ll*s2[i+1]*(xi-x[i])%mod;
ifac[0] = ifac[1] = 1;
for (ll i = 2; i <= n; i++) ifac[i] = -1ll*mod/i*ifac[mod%i]%mod;
for (ll i = 2; i <= n; i++) ifac[i] = 1ll*ifac[i]*ifac[i-1]%mod;
for (ll i = 0; i <= n; i++)
(ans += 1ll*y[i]*(i == 0 ? 1 : s1[i-1])%mod*s2[i+1]%mod
*ifac[i]%mod*(((n-i)&1) ? -1 : 1)*ifac[n-i]%mod) %= mod;
return (ans+mod)%mod;
}
int main(){
ll n,k;
cin>>n>>k;
if(k==0){
cout<<n<<endl;
return 0;
}
p[0]=0;
for(ll i=1;i<=k+2;i++) p[i]=(p[i-1]%mod+qpow(i,k))%mod;
for(ll i=1;i<=k+2;i++) x[i]=i;
if(n<=k+2){
cout<<p[n]<<endl;
}
else{
cout<<lagrange(k+2,x,p,n)<<endl;
}
return 0;
}
总结:
其实拉格朗日插值在算法竞赛中主要用于数据分析,即对于给定的某些关系构造出若干已知点,然后利用这些已知点去计算通项公式。
推荐阅读
-
BZOJ3453: tyvj 1858 XLkxc(拉格朗日插值)
-
BZOJ2655: calc(dp 拉格朗日插值)
-
拉格朗日插值学习小结
-
python数据分析与挖掘实战---拉格朗日插值法
-
BZOJ4559: [JLoi2016]成绩比较(dp 拉格朗日插值)
-
洛谷P4593 [TJOI2018]教科书般的*(拉格朗日插值)
-
计算方法实验(一):拉格朗日插值多项式
-
插值多项式的拉格朗日形式
-
插值与拟合 (一) : 拉格朗日多项式插值 、Newton插值 、分段线性插值、Hermite插值 、样条插值、 B 样条函数插值、二维插值
-
lagrange插值法:求拉格朗日插值多项式matlab实现(内附代码及例题)