题目大意：
有一个长度为n的序列，有三个操作1.I a b c表示将[a,b]这一段区间的元素集体增加c，2.R a b表示将[a,b]区间内所有元素变成相反数，3.Q a b c表示询问[a,b]这一段区间中选择c个数相乘的所有方案的和mod 19940417的值。
思路：
显然需要用线段树维护一个数组sum[c]表示选c个数相乘的方案总和。合并的时候只要枚举c，然后枚举左边选几个数然后和右边的乘起来累加进去就好了。取反实际上就是把所有c为奇数的取反，关键是区间加。对于[l,r]，区间+x，那么枚举c。注意到形式是这样的： newsum[c]=Σ(a1+x)(a2+x)...(ac+x)，然后按照x的次数合并同类项，可以发现这个东西可以通过x^k，组合数C(r-l+1,k)和oldsum[c-k]得到答案。k为x的次数。其余就是普通的线段树了。注意：推标记时要注意顺序。
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define N 150000 5 #define mod 19940417 6 #define ll long long 7 using namespace std; 8 9 int lazy[N],zhs[N][21],size[N]; 10 struct node{int sum[21];}ans[N]; 11 bool rev[N]; 12 13 int read() 14 { 15 int x=0,y=1; 16 char ch=getchar(); 17 while (ch<'0' || ch>'9') {if (ch=='-') y=-1;ch=getchar();} 18 while (ch>='0' && ch<='9') {x=x*10+ch-48;ch=getchar();} 19 return x*y; 20 } 21 22 void add(int &x,int y) 23 { 24 x+=y; 25 if (x>=mod) x-=mod; 26 } 27 28 void up_date(int k) 29 { 30 for (int i=1;i<=20;i++) 31 { 32 ans[k].sum[i]=0; 33 for (int j=1;j<i;j++) add(ans[k].sum[i],(ll)ans[k<<1].sum[j]*ans[k<<1|1].sum[i-j]%mod); 34 add(ans[k].sum[i],ans[k<<1].sum[i]);add(ans[k].sum[i],ans[k<<1|1].sum[i]); 35 } 36 } 37 38 void ins(int k,int val) 39 { 40 add(lazy[k],val); 41 for (int i=20;i;i--) 42 { 43 int x=val,j; 44 for (j=i-1;j;j--,x=(ll)x*val%mod) 45 add(ans[k].sum[i],(ll)x*ans[k].sum[j]%mod*zhs[size[k]-j][i-j]%mod); 46 add(ans[k].sum[i],(ll)x*zhs[size[k]][i]%mod); 47 } 48 } 49 50 void turn(int k) 51 { 52 int i; rev[k]^=1; 53 if (lazy[k]) lazy[k]=mod-lazy[k]; 54 for (i=19;i>0;i-=2) if (ans[k].sum[i]) ans[k].sum[i]=mod-ans[k].sum[i]; 55 } 56 57 void build(int l,int r,int cur) 58 { 59 size[cur]=r-l+1; 60 if (l==r) {ans[cur].sum[1]=read()%mod;return;} 61 int mid=(l+r)>>1; 62 build(l,mid,cur<<1),build(mid+1,r,cur<<1|1),up_date(cur); 63 } 64 65 void push_down(int k) 66 { 67 if (rev[k]) turn(k<<1),turn(k<<1|1),rev[k]=0; 68 if (lazy[k])ins(k<<1,lazy[k]),ins(k<<1|1,lazy[k]),lazy[k]=0; 69 } 70 71 72 void fan(int l,int r,int k,int x,int y) 73 { 74 if (l==x && r==y){ turn(k); return; } 75 int mid=l+r>>1; push_down(k); 76 if (y<=mid) fan(l,mid,k<<1,x,y); 77 else if (x>mid) fan(mid+1,r,k<<1|1,x,y); 78 else fan(l,mid,k<<1,x,mid),fan(mid+1,r,k<<1|1,mid+1,y); 79 up_date(k); 80 } 81 82 void jia(int L,int R,int cur,int l,int r,int val) 83 { 84 if (l==L && r==R) {ins(cur,val);return;} 85 int mid=(L+R)>>1; push_down(cur); 86 if (r<=mid) jia(L,mid,cur<<1,l,r,val); 87 else if (l>mid) jia(mid+1,R,cur<<1|1,l,r,val); 88 else jia(L,mid,cur<<1,l,mid,val),jia(mid+1,R,cur<<1|1,mid+1,r,val); 89 up_date(cur); 90 } 91 92 node ask(int L,int R,int cur,int l,int r,int val) 93 { 94 if (l==L && r==R) return ans[cur]; 95 int mid=(L+R)>>1; push_down(cur); 96 if (l>mid) return ask(mid+1,R,cur<<1|1,l,r,val); 97 else if (r<=mid) return ask(L,mid,cur<<1,l,r,val); 98 else 99 { 100 node x=ask(L,mid,cur<<1,l,mid,val),y=ask(mid+1,R,cur<<1|1,mid+1,r,val),t; 101 for (int i=1;i<=val;i++) 102 { 103 t.sum[i]=(x.sum[i]+y.sum[i])%mod; 104 for (int j=1;j<i;j++) add(t.sum[i],(ll)x.sum[j]*y.sum[i-j]%mod); 105 } 106 return t; 107 } 108 } 109 110 int main() 111 { 112 int n=read(),m=read(),i,j; 113 zhs[0][0]=1; 114 for (i=1;i<=n;i++) 115 { 116 zhs[i][0]=1; 117 for (j=1;j<=i && j<=20;j++) zhs[i][j]=(zhs[i-1][j-1]+zhs[i-1][j])%mod; 118 } 119 build(1,n,1); 120 while (m--) 121 { 122 char ch=getchar(); 123 while (ch<'A' || ch>'Z') ch=getchar(); 124 if (ch=='I') 125 { 126 int x=read(),y=read(),z=read()%mod; 127 if (z<0) z+=mod; jia(1,n,1,x,y,z); 128 } 129 if (ch=='R') 130 { 131 int x=read(),y=read(); 132 fan(1,n,1,x,y); 133 } 134 if (ch=='Q') 135 { 136 int x=read(),y=read(),z=read(); 137 printf("%d\n",ask(1,n,1,x,y,z).sum[z]); 138 } 139 } 140 return 0; 141 }
转载于:https://www.cnblogs.com/HHshy/p/5823354.html
