Lagrange polynomial

Catalog

Common theorems

Example 1

Example 2

---

Common theorems

Theorem 1  Sequence once Difference , Its polynomial degree will -1, The polynomial is n The sequence of powers The prefix and （ Is not necessarily n Time ）, The polynomial degree is n+1

Theorem 2 One p Order arithmetic sequence The general term of its sequence is p Sub polynomial

Example 1

The Sum of the k-th Powers

 

  There are specific solutions for power combination classes , Including Lagrange interpolation

about , Make a difference

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

 b0=1 b1=2^k  b2=3^k ... by k Order arithmetic sequence , be bn The general term is a k Sub polynomial ,an It's a k+1 Sub polynomial

and k+1 Polynomial of degree can be used by us k+1+1 Point to determine , The so-called certainty , It means we k+2 The sum of the results of the operation of points is f(n) Result .

We take 1-->k+2 This is a piece of ,f(i) Can be done k+2 Times fast power to solve accumulatively , The next string , Molecules can make a Prefix suffix product , Molecules are fac[  x[i] -1 ]      +   flag*fac[ x[k+2]- x[i]  ]   flag stay N-x[i] If it is an odd number, take a negative number

# 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;

}

Example 2

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;
}