异或，二进制，真有趣啊。
题目
rating赛的一道二进制题。比赛的时候瞎搞过了，还是记录一下思路。那个时候好菜啊。
题意
给出n个数（n<=1e5），求出这n个数任意子区间的异或值的和。
思路
之前提过，异或这个东西具有非常优良的性质。对于任意子区间[i,j]，如果我们预处理出异或前缀和pre[]数组，显然i到j的异或值为pre[j]^pre[i-1]。但是得到这个还是不够，1e5的数据O(n^2)是不行的。那么我们考虑按位来计算贡献，1e9的二进制位数不会超过30，对于每一位都计算贡献，显然时间复杂度较低。
如何按位计算？我们知道，对于pre[j]^pre[i-1]，只有pre[j]和pre[i-1]的第k位不同时，他们的第k位才会做贡献，那么我们可以固定子区间的右端点r，计算对于每一个r，每一个k，之前的有多少个在第k位和r不一样，这个计算会不会工作量很大呢？不会，假设我们已经知道r时候的情况，那么r+1和r是只区别在r+1这一位的，如果r+1这一位是0，就给做贡献的位数+前面第k位是1的数目，反之，+前面第k位是0的数目。最后2^k*（做贡献的位数）即可，便可得到最终答案。
收获
异或真的是有优良性质，觉得异或的前缀和应该是一个比较常用的工具。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define INF 0x3f3f3f3f
#define maxn 100005
#define maxm 30000
#define ll long long
#define mod 1000000000+7
#define mian main
#define mem(a,b) memset(a,b,sizeof a)
#ifndef ONLINE_JUDGE
#define dbg(x) cout<<#x<<"="<<x<<endl;
#else
#define dbg(x)
#endif
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch<'0' || ch>'9')
{
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0'&&ch <= '9')
{
x = 10 * x + ch - '0';
ch = getchar();
}
return x*f;
}
inline void Out(int a)
{
if (a>9)
Out(a / 10);
putchar(a % 10 + '0');
}
int n;
ll a[maxn],x[maxn],ans1;
int main()
{
n=read();
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
x[i]=x[i-1]^a[i];
}
ans1=0;
for(ll k=0;k<30;++k){
ll cnt[2]={},tmp=0;
for(ll i=0;i<=n;i++){
tmp+=cnt[((x[i]>>k)&1)^1];
++cnt[(x[i]>>k)&1];
}
ans1+=1LL*(1<<k)*tmp;
}
cout<<ans1<<endl;
}
|