传送门 本题求的是区间内的异或和之和，由此可以想到异或前缀和。令
s
u
m
i
=
⊕
k
=
1
i
a
k
sum_{i}={\Large \oplus}^{i}_{k=1}a_k \text{}
sumi=⊕k=1iak（⊕为异或），则区间
[l,r]
\text{[l,r]}
[l,r]的异或和就可以表示为
s
u
m
r
⊕
s
u
m
l
−
1
sum_r \oplus sum_{l-1}
sumr⊕suml−1。 求完异或前缀和之后，原题就变成了“求出n+1个数两两异或之和”。此时，我们可以对这“n+1个数”进行拆位操作。 将
s
u
m
0
sum_0
sum0至
s
u
m
n
sum_n
sumn这n+1个数进行拆位操作，拆出从低往高每一位0和1的个数。例如本题样例：
5
1 2 3 4 5
异或前缀和
s
u
m
i
sum_i
sumi为：
i: 0 1 2 3 4 5
sum[i]: 0 1 3 0 4 1
->(000) (001) (011) (000) (100) (001)
s
u
m
i
sum_i
sumi的每一位：
至于最后的结果怎么算……如果想让某一位的异或值为1，就得让0和1运算。所以，在每一位中，计算有多少种0和1运算的可能就贡献了多少个“1”，再乘上当前位的权重，累加即可。 这里我用
c
n
t
i
,
j
cnt_{i,j}
cnti,j表示（从低往高）第i位（最多21位，i从0开始）是j（0或1）的个数。所以，最终答案为：
a
n
s
=
∑
i
=
0
20
2
i
⋅
c
n
t
i
,
0
⋅
c
n
t
i
,
1
ans=\sum_{i=0}^{20}2^i \cdot cnt_{i,0} \cdot cnt_{i,1}
ans=i=0∑202i⋅cnti,0⋅cnti,1 代码如下：
#include
#define InitInf 63
#define ll long long
#define ud unsigned
#define inf 0x3f3f3f3f
#define Linf 0x3f3f3f3f3f3f3f3f
#define N 21
using namespace std;
ll n,t,a,cnt[N][2],ans;
int main(){
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
cin>>n;
for(ll i=0;i<=20;i++)//把sum[0]处理掉
cnt[i][0]=1;
for(ll i=1;i<=n;i++){
scanf("%lld",&t);
a^=t;//a为异或前缀和
for(ll j=0;j<=20;j++)
cnt[j][a>>j&1]++;//对应位个数加1
}
for(ll i=0;i<=20;i++)
ans+=cnt[i][0]*cnt[i][1]*(1< cout< //fclose(stdin); //fclose(stdout); return 0; } 好文推荐
您阅读本篇文章共花了：
发表评论