比赛时，第二题就是做的这个，当时果断没仔细考虑，直接用线段树暴力求。结果易想而知，超时了。
比赛后搜了搜题解，恍然大悟。
思路：显然用线段树，但是由于每次查询都会有变，所以不可能存储题目中的式子。
这里要注意：k的值非常小，所以应该是将式子按二项式定理展开
(i-L+1)^k=(i+(1-L))^k
展开之后可以发现：我们可以在节点存储ai*i,ai*i^2,ai*i^3,ai*i^4,ai*i^5 (L<=i<=R)的累加和。
至于关于(1-L)^j(j=0~5)可以预先枚举所有的L，预先处理一下用数组存储。
展开式要用到组合，所以组合也要预先处理一下。
当更新时，我们发现l<=i<=r区间中所有的ai都变为x，
累加和分别为x*(L+...+R),x*(L^2+...+R^2),x*(L^3+...+R^3),...,x*(L^5+...+R^5)
因此我们也要预先处理1^j+2^j+...+n^j的和，存到一个数组中去
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue> using namespace std;
const long long mod=;
const int maxn=*;
const int maxnN=;
int n,m,k;
int L,R;
long long ans;
int C[][];
long long S[maxnN][]; //S[i][j]存储(1-i)^j的值
long long LMi[maxnN][]; //LMi[i][j]存储i^j的值，1<=i<=n，即ai*i^j中的i^j
long long sum[maxnN][]; //sum[i][j] 表示1^j+2^j……+i^j的值
struct Node {
int left,right;
long long pow0,pow1,pow2,pow3,pow4,pow5; //powj: ai*i^j的和,j=0~5
bool lazy;
int add;
} tree[maxn]; void init1() {
C[][]=;
for(int i=; i<=; i++) {
C[i][]=;
C[i][i]=;
for(int j=; j<i; j++) {
C[i][j]=C[i-][j-]+C[i-][j];
}
}
} void init2() {
memset(sum,,sizeof(sum));
for(int i=; i<=n; i++) {
S[i][]=;
LMi[i][]=;
sum[i][]=i;
for(int j=; j<=; j++) {
LMi[i][j]=(LMi[i][j-]*i)%mod;
S[i][j]=(S[i][j-]*(-i)%mod+mod)%mod;
sum[i][j]=(sum[i-][j]+LMi[i][j])%mod;
}
}
} void pushUp(int rt) {
tree[rt].pow0=(tree[rt<<].pow0+tree[rt<<|].pow0)%mod;
tree[rt].pow1=(tree[rt<<].pow1+tree[rt<<|].pow1)%mod;
tree[rt].pow2=(tree[rt<<].pow2+tree[rt<<|].pow2)%mod;
tree[rt].pow3=(tree[rt<<].pow3+tree[rt<<|].pow3)%mod;
tree[rt].pow4=(tree[rt<<].pow4+tree[rt<<|].pow4)%mod;
tree[rt].pow5=(tree[rt<<].pow5+tree[rt<<|].pow5)%mod;
} void build(int left,int right,int rt) {
tree[rt].left=left;
tree[rt].right=right;
tree[rt].lazy=false;
tree[rt].add=;
if(left==right) {
scanf("%I64d",&tree[rt].pow0);
tree[rt].pow1=(tree[rt].pow0*LMi[left][])%mod;
tree[rt].pow2=(tree[rt].pow0*LMi[left][])%mod;
tree[rt].pow3=(tree[rt].pow0*LMi[left][])%mod;
tree[rt].pow4=(tree[rt].pow0*LMi[left][])%mod;
tree[rt].pow5=(tree[rt].pow0*LMi[left][])%mod;
return;
}
int mid=(left+right)>>;
build(left,mid,rt<<);
build(mid+,right,rt<<|);
pushUp(rt);
} void pushDown(int rt);
void update(int l,int r,int value,int rt) {
if(l==tree[rt].left && tree[rt].right==r) {
tree[rt].lazy=true;
tree[rt].add=value;
tree[rt].pow0=value*(((sum[r][]-sum[l-][])%mod+mod)%mod);
tree[rt].pow1=value*(((sum[r][]-sum[l-][])%mod+mod)%mod);
tree[rt].pow2=value*(((sum[r][]-sum[l-][])%mod+mod)%mod);
tree[rt].pow3=value*(((sum[r][]-sum[l-][])%mod+mod)%mod);
tree[rt].pow4=value*(((sum[r][]-sum[l-][])%mod+mod)%mod);
tree[rt].pow5=value*(((sum[r][]-sum[l-][])%mod+mod)%mod);
return;
}
pushDown(rt); int mid=(tree[rt].left+tree[rt].right)>>;
if(r<=mid) {
update(l,r,value,rt<<);
} else if(l>mid) {
update(l,r,value,rt<<|);
} else {
update(l,mid,value,rt<<);
update(mid+,r,value,rt<<|);
}
pushUp(rt); } void pushDown(int rt) {
if(tree[rt].lazy && tree[rt].left!=tree[rt].right) {
tree[rt<<].lazy=tree[rt<<|].lazy=true;
long long tmp=tree[rt].add; tree[rt<<].add=tree[rt].add;
tree[rt<<|].add=tree[rt].add; int mid=(tree[rt].left+tree[rt].right)>>;
//这里可以直接调用update方法对儿子进行更新
update(tree[rt].left,mid,tmp,rt<<);
update(mid+,tree[rt].right,tmp,rt<<|); tree[rt].add=;
tree[rt].lazy=false;
}
} long long query(int l,int r,int rt,int i) {
if(l==tree[rt].left && tree[rt].right==r) {
if(i==)
return tree[rt].pow0;
else if(i==)
return tree[rt].pow1;
else if(i==)
return tree[rt].pow2;
else if(i==)
return tree[rt].pow3;
else if(i==)
return tree[rt].pow4;
else if(i==)
return tree[rt].pow5;
}
pushDown(rt); int mid=(tree[rt].left+tree[rt].right)>>;
if(r<=mid) {
return query(l,r,rt<<,i)%mod;
} else if(l>mid) {
return query(l,r,rt<<|,i)%mod;
} else {
return (query(l,mid,rt<<,i)+query(mid+,r,rt<<|,i))%mod;
}
} int main() {
int x;
char ch[]; scanf("%d%d",&n,&m);
init1();
init2(); build(,n,);
for(int i=; i<=m; i++) {
scanf("%s",ch);
if(ch[]=='=') {
scanf("%d%d%d",&L,&R,&x);
update(L,R,x,);
} else {
scanf("%d%d%d",&L,&R,&k);
ans=; //for(int i=0;i<=k;i++){
for(int i=k; i>=; i--) {
//ans=((ans+((query(L,R,1,i)*C[k][i]%mod)*S[L][k-i]%mod))%mod+mod)%mod;
ans=(ans+((query(L,R,,i)*C[k][i]%mod)*S[L][k-i]%mod))%mod; } printf("%I64d\n",ans);
}
}
return ;
}