发布时间：2024-07-31

拉格朗日插值

$n+1$个数确定$n$次多项式, $f(k)=\sum_{i=0}^n y_i \prod \frac{k-x_j}{x_i-x_j}$

O(n^2)版本

int lagrange(int k,vector<int> &X,vector<int> &Y){
    int ans=0;
    int n=X.size();
    for(int i=0;i<n;i++){
        int fz=1,fm=1;
        for(int j=0;j<n;j++){
            if(i==j)continue;
            fz=fz*(k-X[j])%mod;
            fm=fm*(X[i]-X[j])%mod;
        }
        ans=(ans+Y[i]*fz%mod*qpow(fm,mod-2)%mod)%mod;
    }
    return (ans+mod)%mod;
}

O(n)版本

• 如果$x$取值连续，那么把$x_i$换成$i$,$f(k)=\sum_{i=0}^ny_i \prod \frac{k-i}{i-j}$
• 记$pre_i=\prod_{j=0}^i k-j,suf_i=\prod_{j=i}^n k-j$
• $f(k)=\sum_{i=0}^ny_i\frac{pre_{i-1}suf_{i+1}}{fac_{i-1}fac_{n-i}}$,$n-i$为奇数时分母取负

int lagrange(int k,vector<int> &X,vector<int> &Y,int n){
    int ans=0;
    vector<int> pre(n+10),suf(n+10),ifac(n+10);
    pre[0]=(k-X[0])%mod,suf[n+1]=1;
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]*(k-X[i])%mod;
    for(int i=n;i>=0;i--)suf[i]=suf[i+1]*(k-X[i])%mod;
    ifac[0]=ifac[1]=1;
    for(int i=2;i<=n;i++)ifac[i]=-1ll*mod/i*ifac[mod%i]%mod;
    for(int i=2;i<=n;i++)ifac[i]=ifac[i]*ifac[i-1]%mod;
    for(int i=0;i<=n;i++){
        int tmp=Y[i]*(i==0?1:pre[i-1])%mod*suf[i+1]%mod;
        tmp=tmp*ifac[i]%mod*ifac[n-i]%mod;
        if(n-i&1)tmp=mod-tmp;
        ans=(ans+tmp)%mod;
    }
    return (ans+mod)%mod;
}

求$\sum_{i=1}^n i^k$

复杂度$O(k)$

void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> X(k+2),Y(k+2);
    iota(X.begin(),X.end(),1);
    Y[0]=1;
    for(int i=1;i<=k+1;i++)Y[i]=(Y[i-1]+qpow(i+1,k))%mod;
    cout<<lagrange(n,X,Y,k+1);
}