题目描述
blablabla
样例
//异或和的性质
//我们是所有子段的异或和的和 先前缀和求出S0到Sn的前缀和 然后要求子段的异或和
//异或和具有交换律 比如a1^a2^a1^a2^a3 可以交换为a1^a1^a2^a2^a3因为异或和是 对应的位相同是0 不同是1 所以自身和自身异或最后结果是0
//最后那一堆异或结果是a3 所以[L,R]结果是SR^SL-1 那么两层for循环显然会超时
//所以考虑在这么多子段中 每一位为1的情况有多少次 比如第一位为1的情况有多少 那数量乘以这一位的权值就是这一位最后的贡献
//比如这么多子段有50个子段第二位为1 那第二位对ans答案的贡献就是50*2^1 100
//然后求所有子段 要注意一个情况 假如说前面S1异或了S2 那么后面就别S2异或S1了
//所以假如说从S0到S4 他们的第一位分别是0 1 1 0 1
//那么第一位是1 只有0与1异或会对答案进行贡献 只有1个0现在数量为1 第二位1 前面只有一位0 数量为1+1=2
//第三位是0 前面两个2 就是2+2=4 第四位是1 前面是两个0 就是4+2=6 所以这么多子段中 有6个子段的第一位是1 所以就是6*2^0
//那么代码就一边统计现在遍历的第i为0 1 数量 进项相加就可以了 比如遍历到S1 S1第一位是1 此时统计的第一位0的数量为1 那答案贡献就是+1
//然后第一位子段1的数量++ 按照顺序遍历就可以了，不会出现子段贡献数量错误的问题
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20;
int a[N];//统计前缀和
int n;
long long ans;
int main() {
cin >> n;
for (int i = 1; i <= n;i++) {
cin >> a[i];
a[i] = a[i - 1] ^ a[i];
}
for (int i = 0; i < 21;i++) {//题目给的是2的20次方 最多21位
int c0 = 1, c1 = 0;//a[0]的第i位有一个0
long long now=0;//当前位多少子段对答案有贡献
for (int j = 1; j <= n;j++) {//每一个前缀和
if (a[j] >> i & 1)now += c0, c1++;//a[j]>>i位与1(000000001)与为真 表示第i+1位为1 那么方案数就是加上前面有多少个0的情况
else now += c1, c0++;
}
ans += now * (1ll << i);
}
cout << ans;
return 0;
}
算法1
(暴力枚举) O(n2)
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) O(n2)
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
