[关闭]
@zzzc18 2017-09-02T12:14:42.000000Z 字数 3616 阅读 658

bzoj4017 小Q的无敌异或

bzoj BIT


Link:http://www.lydsy.com/JudgeOnline/problem.php?id=4017

题意:有一个长度为 的数列,求其


以及

Solution

对于第一个子问题,按位计算贡献,即计算ans能加多少个

首先我们计算一下前缀异或和

注:以下就以某一位来讨论

我们维护两个值, 的个数以及 的个数
令当前已经计算了 个值的贡献,要计算 的贡献
如果 处前缀异或和这一位是 则贡献要加上先前 的个数,否则要加上 的个数 (显然,想要使对最终答案的贡献为 ,之前一定是 或者
最后ans直接加上 即可

第一问就解决了,时间复杂度


第二个子问题:
答案是异或和,我们不妨按位来考虑,看什么时候会使 的某一位变成
显然,由异或的性质可知,第 位 有奇数个 出现时,最终答案的第 位才为
形式化的,我们有


此时这题复杂度已经比纯暴力好了非常多,对于每一个 统计出所有满足上式的 的个数,但仍然很高
不过由上面的操作统计先前满足条件的个数,想到可以使用树状数组或线段树来维护, 查询

上述式子可以进一步展开,

可以用树状数组分别查询
代码里会看到查询三个值,很诡异,原因见下图
a.png-8.3kB
由之前推的两个式子可知,两条红线之间夹的是不可取的地方,我们需要左右两边的值,如果用BIT存奇偶性,查找三个绿色处的前缀,异或起来就可以了(中间部分有两遍异或,相当与不存在)

最后,每一位统计最终的奇偶性,若为奇数,则


ps: 等价于 //二进制考虑一下


First Code(奇偶性):

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #define LL long long
  5. #define MAXN 100010
  6. #define MOD 998244353
  7. using namespace std;
  8. LL n;
  9. LL sum[MAXN];
  10. LL xsum[MAXN];
  11. LL p[MAXN];
  12. LL ans;
  13. bool tree[MAXN];
  14. int lowbit(int x){
  15. return (x)&(-x);
  16. }
  17. void change(LL pos){
  18. pos++;
  19. if(pos==0)
  20. return;
  21. LL i;
  22. for(i=pos;i<=n+1;i+=lowbit(i))
  23. tree[i]^=1;
  24. }
  25. LL getnum(LL pos){
  26. LL re=0;LL i;
  27. pos++;
  28. for(i=pos;i;i-=lowbit(i))
  29. re^=tree[i];
  30. return re;
  31. }
  32. LL getloc(LL x){
  33. LL l=0,r=n;
  34. LL ans=-1;
  35. while(l<=r){
  36. LL mid=(l+r)>>1;
  37. if(p[mid]<=x){
  38. l=mid+1;
  39. ans=mid;
  40. }
  41. else
  42. r=mid-1;
  43. }
  44. return ans;
  45. }
  46. void solve1(){
  47. LL k;
  48. LL i;
  49. LL cnt[2];
  50. for(k=0;k<=30;k++){
  51. cnt[0]=cnt[1]=0;
  52. LL tmp=0;
  53. for(i=0;i<=n;i++){
  54. bool tt=xsum[i]&(1<<k);
  55. tmp+=cnt[tt^1];
  56. cnt[tt]++;
  57. }
  58. ans += (1<<k) * tmp%MOD;
  59. ans%=MOD;
  60. }
  61. printf("%lld ",ans);
  62. }
  63. void solve2(){
  64. ans=0;
  65. LL i,k;
  66. for(k = 0;(1LL << k) <= sum[n];k++){
  67. LL tmp=0;
  68. for(i=0;i<=n;i++)
  69. p[i] = sum[i] & ((1LL << (k+1)) - 1);
  70. sort(p,p+n+1);
  71. memset(tree,0,sizeof(tree));
  72. for(i=0;i<=n;i++){
  73. LL now = sum[i] & ((1LL << (k + 1)) - 1);
  74. //printf("%lld %lld\n",now,getloc(now));
  75. LL t1=getnum(getloc(now-(1LL<<k)));
  76. LL t2=getnum(getloc(now+(1LL<<k)));
  77. LL t3=getnum(getloc(now));
  78. change(getloc(now));
  79. //printf("--%lld %lld %lld\n",now-(1LL<<k),now+(1LL<<k),now);
  80. //printf("::%lld %lld %lld\n",t1,t2,t3);
  81. tmp^=t1^t2^t3;
  82. }
  83. if(tmp)
  84. ans |= (1LL<<k);
  85. }
  86. printf("%lld\n",ans);
  87. }
  88. int main(){
  89. scanf("%lld",&n);
  90. LL i;
  91. LL x;
  92. for(i=1;i<=n;i++){
  93. scanf("%lld",&x);
  94. xsum[i]=xsum[i-1]^x;
  95. sum[i]=sum[i-1]+x;
  96. }
  97. solve1();
  98. solve2();
  99. return 0;
  100. }

Second Code(统计个数):

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #define LL long long
  5. #define MAXN 100010
  6. #define MOD 998244353
  7. using namespace std;
  8. LL n;
  9. LL sum[MAXN];
  10. LL xsum[MAXN];
  11. LL p[MAXN];
  12. LL ans;
  13. int tree[MAXN];
  14. int lowbit(int x){
  15. return (x)&(-x);
  16. }
  17. void change(LL pos,int v){
  18. pos++;
  19. if(pos==0)
  20. return;
  21. LL i;
  22. for(i=pos;i<=n+1;i+=lowbit(i))
  23. tree[i]+=v;
  24. }
  25. LL getnum(LL pos){
  26. LL re=0;LL i;
  27. pos++;
  28. for(i=pos;i;i-=lowbit(i))
  29. re+=tree[i];
  30. return re;
  31. }
  32. LL getloc(LL x){
  33. LL l=0,r=n;
  34. LL ans=-1;
  35. while(l<=r){
  36. LL mid=(l+r)>>1;
  37. if(p[mid]<=x){
  38. l=mid+1;
  39. ans=mid;
  40. }
  41. else
  42. r=mid-1;
  43. }
  44. return ans;
  45. }
  46. void solve1(){
  47. LL k;
  48. LL i;
  49. LL cnt[2];
  50. for(k=0;k<=30;k++){
  51. cnt[0]=cnt[1]=0;
  52. LL tmp=0;
  53. for(i=0;i<=n;i++){
  54. bool tt=xsum[i]&(1<<k);
  55. tmp+=cnt[tt^1];
  56. cnt[tt]++;
  57. }
  58. ans += (1<<k) * tmp%MOD;
  59. ans%=MOD;
  60. }
  61. printf("%lld ",ans);
  62. }
  63. void solve2(){
  64. ans=0;
  65. LL i,k;
  66. for(k = 0;(1LL << k) <= sum[n];k++){
  67. LL tmp=0;
  68. for(i=0;i<=n;i++)
  69. p[i] = sum[i] & ((1LL << (k+1)) - 1);
  70. sort(p,p+n+1);
  71. memset(tree,0,sizeof(tree));
  72. for(i=0;i<=n;i++){
  73. LL now = sum[i] & ((1LL << (k + 1)) - 1);
  74. change(getloc(now),1);
  75. LL t1=getnum(getloc(now-(1LL<<k)));
  76. LL t2=getnum(getloc(now+(1LL<<k)));
  77. LL t3=getnum(getloc(now));
  78. tmp+=t1+t2-t3;
  79. }
  80. if(tmp%2)
  81. ans |= (1LL<<k);
  82. }
  83. printf("%lld\n",ans);
  84. }
  85. int main(){
  86. scanf("%lld",&n);
  87. LL i;
  88. LL x;
  89. for(i=1;i<=n;i++){
  90. scanf("%lld",&x);
  91. xsum[i]=xsum[i-1]^x;
  92. sum[i]=sum[i-1]+x;
  93. }
  94. solve1();
  95. solve2();
  96. return 0;
  97. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注