Description

在加里敦中学的小明最近爱上了数学竞赛,很多数学竞赛的题都是与序列的连续和相关的。
所以对于一个序列,求出它们所有的连续和来说,小明觉得十分的简单。但今天小明遇到了
一个序列和的难题,这个题目不仅要求你快速的求出所有的连续和,还要快速的求出这些连
续和的异或值。小明很快的就求出了所有的连续和,但是小明要考考你,在不告诉连续和的
情况下,让你快速求是序列所有连续和的异或值。

Input

第一行输入一个n,表示这序列的数序列 第二行输入n个数字a1,a2…an代表这个序列
0<=a1,a2,…an,0<=a1+a2…+an<=10^6
1<=n <= 10^5

Output

输出这个序列所有的连续和的异或值

Sample Input

3
1 2 3

Sample Output

0

HINT

Source

树状数组:

仍然预处理前缀和

考虑按位维护答案 如果只考虑这一位的话 那么我考虑枚举每个前缀作为终点 然后再去枚举前面的前缀作为起点的情况 那考虑竖式加减法的操作 考虑我当前这一位如果是1  那么我就需要在前面找一个当前这一位是0的位置 并且(0~k-1)位所构成的数需要小于等于我(0~k-1)位所构成的数 或者 找前面第k位是1 并且(0~k-1)位构成的数比我(0~k-1)位所构成的数要大 都是答案

另外一种情况如果我这一位是1 同理

那么我就需要在前面找一个当前这一位是1的位置 并且(0~k-1)位所构成的数需要小于等于我(0~k-1)位所构成的数 或者 找前面第k位是0 并且(0~k-1)位构成的数比我(0~k-1)位所构成的数要大 都是答案

考虑快速维护这个有多少个 就使用权值树状数组即可 可能会出现0等情况 提前判断+1即可

注意存在前缀和为0的情况..

 

考虑每种权值出现的情况 设sn表示所有权值的前缀和 那么这个显然可以用所有前缀表示所有的区间和 那么设$A(x)=1+x^{1}+x^{2}+…x^{sn}$ $B(x)=1+x^{1}+x^{2}+…x^{sn}$ 最后答案是$\sum\limits_{j=1}^{n}\sum\limits_{i=1}^{sn-j}a[i]*b[i+j]$ 于是参考快速傅里叶2 那么直接将其中一个串反过来ntt即可 但是bzoj过不去..正解仍待更新..

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论