题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2962
如果 _，_，_，…… 变成了 (_+k)，(_+k)，(_+k)，…… ，计算就是在每个括号里选 _ 或 k ，乘起来求和。
为了算那个，枚举选了 j 个 k ；剩下那部分的乘积就是sm[cr][ i-j ]！j 和 k 可以在 len 里除了那 i-j 个位置里选，所以乘上 k^j 再乘上 C( len-(i-j) , j ) 。
调了2h+竟然只因组合数推导公式写错……
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=5e4+5,Lm=20,mod=19940417; int n,q,t[N],tot,c[N][Lm+5],ans[Lm+5],tmp[Lm+5]; int ls[N<<1],rs[N<<1],add[N<<1],sm[N<<1][Lm+5]; bool rev[N<<1]; char ch; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return fx?ret:-ret; } void upd(int &x){x-=(x>=mod?mod:0);} void init() { c[0][0]=1; for(int i=1;i<=n;i++)//n! for(int j=0;j<=i&&j<=Lm;j++) { c[i][j]=c[i-1][j]; if(j)c[i][j]+=c[i-1][j-1],upd(c[i][j]);//i-1 } } void pshp(int cr,int l,int mid,int r) { int lm=min(r-l+1,Lm),Ls=ls[cr],Rs=rs[cr]; for(int i=0;i<=lm;i++) { sm[cr][i]=0; for(int j=0;j<=i;j++) sm[cr][i]=(sm[cr][i]+(ll)sm[Ls][j]*sm[Rs][i-j])%mod; } // printf("pshp l=%d r=%d ",l,r); // for(int i=0;i<=lm;i++) // printf(" sm[%d][%d]=%d ",cr,i,sm[cr][i]); } void updt(int cr,int k,int len) { add[cr]+=k; upd(add[cr]); int lm=min(Lm,len); for(int i=lm;i>=0;i--) for(int j=1,ml=k;j<=i;j++,ml=(ll)ml*k%mod)//j=1 //j<=i not j<=lm { sm[cr][i]=(sm[cr][i]+(ll)sm[cr][i-j]*ml%mod*c[len-i+j][j])%mod; // if(cr==3&&i==2) // printf("smi=%d j=%d sm[i-j]=%d ml=%d c=[%d][%d]=%d ",sm[cr][i],j,sm[cr][i-j],ml,len-i+j,j,c[len-i+j][j]); } // printf("updt "); // for(int i=0;i<=lm;i++) // printf(" sm[%d][%d]=%d ",cr,i,sm[cr][i]); } void updr(int cr,int lm) { if(add[cr])add[cr]=mod-add[cr]; rev[cr]^=1;//add for(int i=1;i<=lm;i+=2) if(sm[cr][i]) sm[cr][i]=mod-sm[cr][i]; // printf("updr "); // for(int i=0;i<=lm;i++) // printf(" sm[%d][%d]=%d ",cr,i,sm[cr][i]); } void pshd(int cr,int l,int mid,int r) { int Ls=ls[cr],Rs=rs[cr]; if(rev[cr]) { rev[cr]=0; updr(Ls,min(mid-l+1,Lm)); updr(Rs,min(r-mid,Lm)); } if(add[cr]) { int k=add[cr]; add[cr]=0; updt(Ls,k,mid-l+1); updt(Rs,k,r-mid); } } void build(int l,int r,int cr) { if(l==r){sm[cr][1]=t[l];sm[cr][0]=1;return;} int mid=l+r>>1; ls[cr]=++tot; build(l,mid,ls[cr]); rs[cr]=++tot; build(mid+1,r,rs[cr]); pshp(cr,l,mid,r); } void mdfy(int l,int r,int cr,int L,int R,int v) { if(l>=L&&r<=R) { // printf("mdf: cr=%d l=%d r=%d ",cr,l,r); updt(cr,v,r-l+1); return; } int mid=l+r>>1; pshd(cr,l,mid,r); if(L<=mid) mdfy(l,mid,ls[cr],L,R,v); if(mid<R) mdfy(mid+1,r,rs[cr],L,R,v); pshp(cr,l,mid,r); } void revs(int l,int r,int cr,int L,int R) { if(l>=L&&r<=R) { // printf("rev: cr=%d l=%d r=%d ",cr,l,r); updr(cr,min(r-l+1,Lm)); return; } int mid=l+r>>1; pshd(cr,l,mid,r); if(L<=mid) revs(l,mid,ls[cr],L,R); if(mid<R) revs(mid+1,r,rs[cr],L,R); pshp(cr,l,mid,r); } void query(int l,int r,int cr,int L,int R,int k) { if(l>=L&&r<=R) { int lm=min(k,r-l+1); for(int i=k;i>=0;i--) for(int j=1;j<=lm&&j<=i;j++)//j<=i ans[i]=(ans[i]+(ll)sm[cr][j]*ans[i-j])%mod; return; } int mid=l+r>>1; pshd(cr,l,mid,r); if(L<=mid) query(l,mid,ls[cr],L,R,k); if(mid<R) query(mid+1,r,rs[cr],L,R,k); } int main() { // freopen("data.in","r",stdin); n=rdn(); q=rdn(); init(); for(int i=1;i<=n;i++) t[i]=rdn()%mod+mod,upd(t[i]); tot=1; build(1,n,1); ans[0]=1; for(int i=1,a,b,c;i<=q;i++) { cin>>ch;scanf("%d%d",&a,&b); if(ch!='R')scanf("%d",&c); if(ch=='I') { c=c%mod+mod; upd(c); mdfy(1,n,1,a,b,c); } if(ch=='R') revs(1,n,1,a,b); if(ch=='Q') { for(int i=1;i<=c;i++)ans[i]=0; query(1,n,1,a,b,c); printf("%d ",ans[c]); } } return 0; }