解题思路
过3个点——维护前缀和$O(n^2)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n;
int a[N];
int s[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
s[i]=s[i-1]^a[i];
LL res=0;
for(int len=1;len<=n;len++)
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
res+=s[r]^s[l-1];
}
cout<<res;
return 0;
}
AC-按位贡献 $O(k*n)$
按位贡献
由于异或运算是按位进行计算,因此每一位的结果只与这一位1的奇偶性相关,因此又被称为“不进位加法”,因此我们的优化从每一位开始考虑,如果能将一维循环优化为答案的位数k,就可以过掉该题。
假设将所有的数全部异或起来最多有k位二进制位(本题中为21位)
数组a为:a[0]=0(000)【留空】,a[1]=1(001),a[2]=2(010),a[3]=3(011),a[4]=4(100)
前缀异或和数组s为:s[0]=0(000)【留空】,s[1]=1(001),s[2]=3(011),s[3]=0(000),s[4]=4(100)
我们枚举k(1~3)位,枚举区间右边界j(1~4):
当k=1时:
j=1有,s[1]的第1位为1,而s[1]前只有s[0]的的第1位为0,因此k=1该位的贡献为$1*2^0=1$,对应异或区间为s[1]^s[0]
j=2有,s[2]的第1位为1,而s[2]前只有s[0]的的第1位为0,因此k=1该位的贡献为$1+1*2^0=2$,对应异或区间为s[1]^s[0]+s[2]^s[0]
j=3有,s[3]的第1位为0,而s[3]前只有s[1],s[2]的的第1位为1,因此k=1该位的贡献为$2+1*2^0=4$,对应异或区间为s[1]^s[0]+s[2]^s[0]+s[3]^s[1]+s[3]^s[2]
......
当k=2时
j=1有,s[1]的第2位为0,而s[1]前没有第2位为1,因此k=2该位无贡献
j=2有,s[2]的第2位为1,而s[2]前有s[0],s[1]的的第2位为0,因此k=2该位的贡献为$2*2^1=4$,对应异或区间为s[2]^s[0]+s[2]^s[1]
j=3有,s[3]的第2位为0,而s[3]前只有s[2]的的第2位为1,因此k=2该位的贡献为$4+1*2^1=6$,对应异或区间为s[2]^s[0]+s[2]^s[1]+s[3]^s[2]
......
以此类推,我们就可以求出最终的所有异或和
AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n;
int a[N];
int s[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
s[i]=s[i-1]^a[i];
LL res=0;
for(int k=0;k<21;k++)
{
int cnt_0=1,cnt_1=0; //勿忘s[0]
LL t=0; //贡献
for(int j=1;j<=n;j++)
if(s[j]>>k&1)
{
t+=cnt_0;
cnt_1++;
}
else
{
t+=cnt_1;
cnt_0++;
}
res+=t*(1<<k);
}
cout<<res;
return 0;
}