拉格朗日插值法

目录

常用定理

例题一

例题二

---

常用定理

定理1 数列进行一次差分，其多项式次数会-1，多项式为n次幂的数列进行前缀和（不一定是n次），结果多项式次数为n+1

定理2 一个p阶等差数列其数列通项是一个p次多项式

例题一

The Sum of the k-th Powers

 

 幂合类有特定解法，其中就包含拉格朗日插值法

对于,做一次差分

a1=1  a2=1+2^k  a3=1+2^k+3^k  a4...

 b0=1 b1=2^k  b2=3^k ...为k阶等差数列，则bn通项是一个k次多项式,an是一个k+1次多项式

而k+1次多项式又可以被我们用k+1+1个点进行确定，所谓确定，意思是我们k+2个点进行运算的结果之和就是f(n)的结果。

我们取1-->k+2这一段，f(i)可以进行k+2次快速幂进行累加求解，后面的一串，分子可以搞一个前缀后缀积，分子其实就是fac[  x[i] -1 ]      +   flag*fac[ x[k+2]- x[i]  ]   flag在N-x[i]为奇数时取负数

# include<iostream>
# include<complex.h>
# include<string.h>
# include<cstring>
# include<vector>
# include<algorithm>
using namespace std;
typedef complex<double>cp;
# define mod 1000000007
typedef long long int ll;

ll quick(ll base, ll pow)
{
    ll ans=1;

    while(pow)
    {
        if(pow&1)
        {
            ans=ans*base%mod;

        }

        base=base*base%mod;

        pow>>=1;

    }

    return ans;

}

ll fac[1000000+10];

ll pre[1000000+10],bac[1000000+10];

int main ()
{
    ll n,k;

    cin>>n>>k;

    ll ans=0;

    ll temp=0;
    fac[0]=1;
    pre[0]=1;
    for(int i=1; i<=k+2; i++)
    {
        fac[i]=((fac[i-1]*i)%mod+mod)%mod;

        pre[i]=(pre[i-1]*(n-i)%mod+mod)%mod;

    }

    bac[k+3]=1;

    for(int i=k+2; i>=1; i--)
    {
        bac[i]=(bac[i+1]*(n-i)%mod+mod)%mod;

    }

    for(int i=1; i<=k+2; i++)
    {
        temp=(temp+quick(i,k))%mod;




        ll shang=pre[i-1]*bac[i+1]%mod;


        int flag=1;

        if((k+2-i)&1)
            flag=-1;

        ll xia=((fac[i-1]*flag*fac[k+2-i])%mod+mod)%mod;

        xia=quick(xia,mod-2);

        ans=(ans+temp*shang%mod*xia%mod)%mod;

        //cout<<ans<<endl;


    }

    cout<<ans;


    return  0;

}

例题二

Polynomial

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=9999991;
const int N=1e3+10;
int t,n,m,l,r;
int a[N],sum[N],pre[N],suf[N];
int fac[N],finv[N];
int modpow(int x,int n,int p)
{
	int res=1;
	for(;n;x=1ll*x*x%p,n>>=1)
	if(n&1)res=1ll*res*x%p;
	return res;
} 
int cal(int *f,int mx,ll n)
{   
	if(n<=mx)return f[n];
        int ans=0;
	pre[0]=suf[mx]=1;
	for(int i=1;i<=mx;++i)
	pre[i]=1ll*(n-i+1)%mod*pre[i-1]%mod;
	for(int i=mx;i>=1;--i)
	suf[i-1]=1ll*(n-i)%mod*suf[i]%mod;
	for(int i=0;i<=mx;++i)
	{
		int sg=(mx-i)&1?-1:1;
		ans=ans+1ll*sg*pre[i]%mod*suf[i]%mod*finv[i]%mod*finv[mx-i]%mod*f[i]%mod;
		if(ans>=mod)ans-=mod;
		if(ans<0)ans+=mod;
	}
    return ans;
}
void init()
{
	fac[0]=1;
	for(int i=1;i<N;++i)
	fac[i]=1ll*fac[i-1]*i%mod;
	finv[N-1]=modpow(fac[N-1],mod-2,mod);
	for(int i=N-1;i>=1;--i)
	finv[i-1]=1ll*finv[i]*i%mod;
}
int main()
{
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++)
        scanf("%d",&a[i]);
        a[n+1]=cal(a,n,n+1);
        sum[0]=a[0]; 
        for(int i=1;i<=n+1;i++)
        sum[i]=(sum[i-1]+a[i])%mod;
        while(m--)
	    {
            scanf("%d%d",&l,&r);
            int cnt=cal(sum,n+1,r)-cal(sum,n+1,l-1);
            if(cnt<0)cnt+=mod;
            printf("%d\n",cnt);
        }
    }
    return 0;
}