拉格朗日插值法

2019-10-09 / 无评论

拉格朗日插值法属于那种不会就是不会,但是上手不是很难的算法。这种算法在ICPC中性价比很高,属于还是很有必要准备一份板子了解一下的东西。

简介

给定n + 1横坐标不相同的点,可以唯一确定一个n次的多项式。那么如何求出这个多项式?最直观的做法就是列方程求解。但是这样需要\Theta(n^3)的时间来计算。而拉格朗日插值法则通过构造的方法,得到了一个经过n + 1个点的n次多项式。 具体的过程是这样的,假设现在我们得到了n + 1个点:

(x_0, y_0), \;(x_1, y_1),\; \dots,\;(x_n, y_n)

拉格朗日基本多项式为:

\ell_j(x) = \prod_{i = 0, i \neq j}^n {x - x_i \over x_j - x_i} \tag{1.1}

这个基本多项式构造十分巧妙,因为注意到\ell_j(x_j) = 1,并且\ell_j(x_i) = 0, \;\forall i \neq j。那么,接着构造出这个n次多项式:

P(x) = \sum_{i = 0}^n y_i\ell_i(x) \tag{1.2}

根据基本多项式的性质,我们可以知道P(x_i) = y_i,也就是经过了这n + 1个点。 通过简单的多项式乘法和多项式除法就可以在\Theta(n^2)的时间求出这个多项式的系数表达。

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
typedef long long ll;
ll a[2010],b[2010];
ll n,k;
ll inv(ll a,ll m){
    if(a==1)return 1;
    return inv(m%a,m)*(m-m/a)%m;
}
int main(){
    scanf("%lld%lld",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d %d",&a[i],&b[i]);
    }
    ll ans = 0;
    for(int t=0;t<=n-1;t++){
        ll s1,s2;s1 =s2 =1;
        for(int i=0;i<=n-1;i++){
            if(i!=t){
                s1*=(k-a[i]+mod)%mod;
                s2*=(a[t]-a[i]+mod)%mod;
                s1 = s1%mod;
                s2 = s2%mod;
            }
        }
        ans+=(b[t]*s1%mod*inv(s2,mod)%mod);
        ans = ans%mod;
    }
    cout << ans << endl;
}

无回应:“拉格朗日插值法”

发表评论

电子邮件地址不会被公开。 必填项已用*标注