南昌邀请赛B题（拉格朗日插值）

题目链接：https://nanti.jisuanke.com/t/40254

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;
const int N=1e3+100;
const int P=9999991;
ll pre[N], suf[N], ifac[N],sum[N],a[N],fac[N];
ll Pow(ll x, int t)
{
    ll res=1;
    while (t)
    {
        if (t&1) res=(x*res)%P;
        x=x*x%P; t>>=1;
    }
    return res;
}
void init(int n)
{
     fac[0]=1;
    for(int i=1;i<=n+2;i++)
    {
        fac[i]=fac[i-1]*i%P;
    }
    for(int i=0;i<=n+2;i++)
    {
        ifac[i]=Pow(fac[i],P-2);
    }
}
ll Lagrange(ll *y,ll n,ll k)
{
    ll ans=0; pre[0]=1;suf[n+1]=1;
    for (int i=0; i<=n; i++) pre[i+1]=1ll*pre[i]*(k-i)%P;
    for (int i=n; i>=0; i--) suf[i]=1ll*suf[i+1]*(k-i)%P;

    for (int i=0; i<=n; i++)
    {
        ll temp=y[i]*pre[i]%P*suf[i+1]%P*ifac[i]%P*ifac[n-i]%P;
        if((n-i)&1)
            ans=(ans-temp)%P;
        else
            ans=(ans+temp)%P;
    }
    return (ans%P+P)%P;
}

int main()
{
   ll T,n,m,L,R;
   cin>>T;
   init(1020);
   while(T--)
   {
       cin>>n>>m;
       for(int i=0;i<=n;i++)
       {
           cin>>a[i];
       }
       a[n+1]=Lagrange(a,n,n+1);
       sum[0]=a[0]%P;
       for(int i=1;i<=n+1;i++)
       {
           sum[i]=(sum[i-1]+a[i])%P;
       }
       for(int j=1;j<=m;j++)
       {
           cin>>L>>R;
           ll ans=Lagrange(sum,n+1,R)-Lagrange(sum,n+1,L-1);
           cout<<(ans+P)%P<<"\n";
       }
   }
    return 0;
}