题解|#智乃酱的静态数组维护问题多项式 #

题目链接：https://ac.nowcoder.com/acm/contest/19483/D
简要题意：给出一个不超过5阶的多项式，再给出一个数组a。m次修改，每次找一段区间[L,R]，给区间里的每个数分别加上f(1),f(2),...,f(r-l+1)
利用数学定理：最高次项为n次的n阶多项式差分后余项为常数。因此，f做6次差分后，余项为一串0
（也可通过如下打表寻找规律）

所以，我们可以先把a做6阶差分，再把每次出来的函数f也做6阶差分，将其加入a中。
这样就能保证每次加入a的是有限项（我是算了15项），从而将O(NM)的复杂度降到O(M)
需要注意的是，f加入a的有效区间是[L,n],n为数组a的长度。因此，还需要一个函数g，g加入a的区间是[R+1,n]，而且g(x)=-f(x+r-l+1)，保证在后面抵消掉f
最后将a的6阶差分求和7次，就能得到a的前缀和了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define _for(i,a,b)    for(int i=(a);i<=(b);i++)
#define _rep(i,a,b)    for(int i=(a);i>=(b);i--)
const int N=1e5+10;
const ll mod=1e9+7;
ll n,m,q;
ll a[N];
void P(ll a[],int len,int cnt){//将a[1]到a[len]做cnt次求和
    while(cnt--){
        _for(i,1,len){
            a[i]+=a[i-1];
            if(a[i]>=mod)    a[i]-=mod;
        }    
    }
}
void D(ll a[],int len,int cnt){//将a[1]到a[len]做cnt次差分
    while(cnt--){
         _rep(i,len,1){//差分数组要倒序求
            a[i]-=a[i-1];
            if(a[i]<0)    a[i]+=mod;
        }
    }
}
ll f(ll a[],int x,int k){//a为多项式函数f的系数，k为f最高次数
    ll base=1;
    ll ans=0;
    _for(i,0,k){
        ans+=a[i]*base%mod;//相乘后要取模
        if(ans>=mod)    ans-=mod;
        base=base*x%mod;
    }
    return ans;
}
ll g(ll a[],int x,int k,int l,int r){
    return (mod-f(a,x+r-l+1,k))%mod;
}
ll ki[10];
ll coef1[20];
ll coef2[20];
int main(){
    scanf("%lld %lld %lld",&n,&m,&q);
    _for(i,1,n)    scanf("%lld",&a[i]);
    D(a,n,6);//原数组做6次差分
    while(m--){
        ll l,r,k;
        scanf("%lld %lld %lld",&l,&r,&k);
        _rep(i,k,0)    scanf("%lld",&ki[i]);
        _for(i,1,15){//做6阶差分后，后面将有一串0.因此这里只需计算前几项就好
            coef1[i]=f(ki,i,k);
            coef2[i]=g(ki,i,k,l,r);
        }
        D(coef1,15,6);
        D(coef2,15,6);
        _for(i,1,15){
            a[l+i-1]+=coef1[i];
            if(a[l+i-1]>=mod)    a[l+i-1]-=mod;
            a[r+i]+=coef2[i];
            if(a[r+i]>=mod)    a[r+i]-=mod;
        }
    }
    P(a,n,7);//6阶差分求和7次，变成前缀和
    while(q--){
        ll l,r;
        scanf("%lld %lld",&l,&r);
        printf("%lld\n",(a[r]-a[l-1]+mod)%mod);
    }
    return 0;
}