发出了龟龟的声音
我们要把所有子段和异或起来
这种东西套路起来就是前缀和加按位考虑呗
首先前缀和可以让我们得到(n^2)的(20)分
然后再考虑按位，我们发现只要计算第(k)位上(1)出现的次数
严格来说是
[ans=sumlimits_{k=0}^{63}*((sumlimits_{i=1}^{n}sumlimits_{j=1}^{i}(s[i]-s[j]-1)>>k&1)\%2)*2^k
]
所以我们只要知道每一位上(1)出现的次数的奇偶
因为减法会进位，所以要考虑上
我们设(s[i]_k)表示第(k)位是(0/1)，(s[i]_{1~k})表示(s[i])从第(1)位到第(k)位的大小
如果(s[i])的第(k)位是(1)，那么对答案有贡献的情况是
(1.s[j]_k=0)且(s[j]_{1~k-1}<=s[i]_{1~k-1})
(2.s[j]_k=1)且(s[j]_{1~k-1}>s[i]_{1~k-1})
如果是(0)
(1.s[j]_k=1)且(s[j]_{1~k-1}<=s[i]_{1~k-1})
(2.s[j]_k=0)且(s[j]_{1~k-1}>s[i]_{1~k-1})
发现(sum a[i])比较小，考虑开两个权值树状数组，存当前位为(0/1)时某个(s[i]_{1~k})的值的数量
方法二：神鱼的多项式科技
设(f_i)为每个数出现的次数，(s_i)为前缀和中(i)出现的次数，(m=sum a[i])
那么
(f_i=sumlimits_{j=0}^{m-i}s_j*s_{j+i})
变形一下
(f_{m-i}=sumlimits_{j=0}^{i}s_j*s_{m-i+j})
右边这个东西看起来挺像卷积的。。我们把它卷一下就得到了(f)数组的翻转
然后看哪个数字出现了偶数次异或起来