题目描述
给一个长度为n的数组,求所有子段的异或和的总和
样例
blablabla
算法1
二进制拆位+贡献法
由数据范围,每个数的二进制位最多有20位
由异或的性质,一个数异或0不会发生改变,奇数个1异或结果为1,偶数个1异或为0
因此,可以针对所有数的二进制的前20位,统计第i个二进制位时,计算1的总个数,若为奇数则有贡献,偶数则无贡献
时间复杂度 O(20n)
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int n;
int a[100010];
ll s[100010];//s[i]表示某一二进制位1的个数的前缀和,共统计20位
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
ll res=0;
for(int i=20;i>=0;i--)//对前20个二进制位讨论
{
memset(s,0,sizeof s);
ll odd=0;
ll even=0;
for(int j=1;j<=n;j++)//拆解每个数的第i个二进制位
{
ll u=(a[j]>>i)&1;//将a[j]的第i个二进制位移到最后一位
s[j]=s[j-1]+u;
//第i位对答案的贡献为1<<i
if(s[j]%2) res+=(1<<i)*(even+1),odd++;//s[j]是奇数,则统计s[1~j-1]中偶数的个数(相减为奇数,则有贡献),+1是因为不选前面的任何数,即把前j个数都选上也合理
else res+=(1<<i)*odd,even++; //s[j]是偶数,则统计s[1~j-1]中奇数的个数,这里不加1是因为偶数本身没有贡献
}
}
cout<<res;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla