首页 > 代码库 > bzoj2962 序列操作 题解
bzoj2962 序列操作 题解
题目大意：
有一个长度为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 }
bzoj2962 序列操作 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。