本文共 3356 字，大约阅读时间需要 11 分钟。
因为$k$比较小，对于序列的每个位置，维护出$a_{i}*i^{k}$的值，并用线段树维护区间和。因为存在区间赋值操作，我们再维护$f[i][j]$表示$\sum\limits_{x=1}^{i}x^j$(即$j$次幂的前缀和)，用两个前缀和相减即可得到区间对应需要乘的数。对于询问，我们先求出区间中维护的各次幂的和，例如当$k=2$时，$ans=\sum a_{i}*i^2-2*(l-1)\sum a_{i}*i+(l-1)^2\sum a_{i}$，暴力将各次幂的和乘上对应常数相加即为答案。其他的$k$的情况同理，根据二项式展开推一下即可。
#include #include #include #include #include #include #include #include #include #include #include #define ll long long#define mod 1000000007using namespace std;ll s[100010][6];ll sum[400010][6];ll num[400010];ll ans[6];int n,m;int x,k;char ch[3];int l,r;ll calc(int l,int r,int k){ return ((s[r][k]-s[l-1][k])%mod+mod)%mod;}void pushup(int rt){ for(int i=0;i<=5;i++) { sum[rt][i]=sum[rt<<1][i]+sum[rt<<1|1][i]; }}void pushdown(int rt,int l,int r){ if(num[rt]!=-1) { int mid=(l+r)>>1; num[rt<<1]=num[rt]; num[rt<<1|1]=num[rt]; for(int i=0;i<=5;i++) { sum[rt<<1][i]=num[rt]*calc(l,mid,i)%mod; sum[rt<<1|1][i]=num[rt]*calc(mid+1,r,i)%mod; } num[rt]=-1; }}void build(int rt,int l,int r){ num[rt]=-1; if(l==r) { scanf("%d",&x); for(int i=0;i<=5;i++) { sum[rt][i]=1ll*x*calc(l,l,i)%mod; } return ; } int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); pushup(rt);}void change(int rt,int l,int r,int L,int R,int k){ if(L<=l&&r<=R) { num[rt]=1ll*k; for(int i=0;i<=5;i++) { sum[rt][i]=1ll*k*calc(l,r,i)%mod; } return ; } pushdown(rt,l,r); int mid=(l+r)>>1; if(L<=mid) { change(rt<<1,l,mid,L,R,k); } if(R>mid) { change(rt<<1|1,mid+1,r,L,R,k); } pushup(rt);}void query(int rt,int l,int r,int L,int R){ if(L<=l&&r<=R) { for(int i=0;i<=5;i++) { ans[i]+=sum[rt][i]; ans[i]%=mod; } return ; } pushdown(rt,l,r); int mid=(l+r)>>1; if(L<=mid) { query(rt<<1,l,mid,L,R); } if(R>mid) { query(rt<<1|1,mid+1,r,L,R); }}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { s[i][0]=1ll; for(int j=1;j<=5;j++) { s[i][j]=s[i][j-1]*i%mod; } } for(int i=1;i<=n;i++) { for(int j=0;j<=5;j++) { s[i][j]+=s[i-1][j]; s[i][j]%=mod; } } build(1,1,n); while(m--) { scanf("%s%d%d%d",ch,&l,&r,&k); if(ch[0]=='=') { change(1,1,n,l,r,k); } else { memset(ans,0,sizeof(ans)); query(1,1,n,l,r); ll res=0; if(k==0) { res+=ans[0],res%=mod; } else if(k==1) { res+=ans[1],res%=mod; res-=1ll*(l-1)*ans[0]%mod,res%=mod; } else if(k==2) { res+=ans[2],res%=mod; res-=2ll*(l-1)*ans[1]%mod,res%=mod; res+=1ll*(l-1)*(l-1)%mod*ans[0]%mod,res%=mod; } else if(k==3) { res+=ans[3],res%=mod; res-=3ll*(l-1)*ans[2]%mod,res%=mod; res+=3ll*(l-1)*(l-1)%mod*ans[1]%mod,res%=mod; res-=1ll*(l-1)*(l-1)%mod*(l-1)%mod*ans[0]%mod,res%=mod; } else if(k==4) { res+=ans[4],res%=mod; res-=4ll*(l-1)*ans[3]%mod,res%=mod; res+=6ll*(l-1)*(l-1)%mod*ans[2]%mod,res%=mod; res-=4ll*(l-1)*(l-1)%mod*(l-1)%mod*ans[1]%mod,res%=mod; res+=1ll*(l-1)*(l-1)%mod*(l-1)%mod*(l-1)%mod*ans[0]%mod,res%=mod; } else { res+=ans[5],res%=mod; res-=5ll*(l-1)*ans[4]%mod,res%=mod; res+=10ll*(l-1)*(l-1)%mod*ans[3]%mod,res%=mod; res-=10ll*(l-1)*(l-1)%mod*(l-1)%mod*ans[2]%mod,res%=mod; res+=5ll*(l-1)*(l-1)%mod*(l-1)%mod*(l-1)%mod*ans[1]%mod,res%=mod; res-=1ll*(l-1)*(l-1)%mod*(l-1)%mod*(l-1)%mod*(l-1)%mod*ans[0]%mod,res%=mod; } res=(res%mod+mod)%mod; printf("%lld\n",res); } }}
转载于:https://www.cnblogs.com/Khada-Jhin/p/10446448.html