题目链接: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; }