题面描述
连续和的异或值。
题解
题目实际要求出
\[
\begin{aligned}
ans\ =\ \oplus \sum_{i=1}^n\sum_{j=0}^{i-1}sum_i-sum_j
\end{aligned}
\]
然后，我看了一下二进制加法器后直接弃疗
实际上，几乎所有二进制题都是按位考虑的
我们把它改写成按位考虑的形式
\[
\begin{aligned}
ans = \sum_{k=0}^{2^k\le sum_n} (
\sum_{i=1}^n\sum_{j=0}^{i-1}(sum_i-sum_j)>>k\& 1\ (mod 2)
)<<k
\end{aligned}
\]
按位考虑后实际上就是对于 \(sum_i\)
而言， 前面有多少 \(sum_j\) 与 \(sum_i\) 差在 \(k\) 为 \(1\)
当 \(sum_i\) 这一位为 \(1\) 则差仍为此的情况必定为 \(sum_j\) 这一位为 \(0\) 且之前没有借位
另一种情况恰好相反
所以问题在于是否借位，考虑竖式计算的过程，发现 当且仅当 \(sum_i \&(2^k-1)\ \ge\
sum_j\&(2^k-1)\) 不会借位
用权值树状数组维护一下就好了
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
typedef long long int64;
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 2e6+5;
int n, m, sum[N];
struct Fenwick
{
int64 c[N];
void clear() { memset(c, 0, sizeof(c)); }
void add(int x) { ++x; for( ; x <= m+1; x += x&-x) ++c[x]; }
int64 ask(int x) { int ret = 0 ; ++x; for( ; x; x -= x&-x) ret += c[x]; return ret; }
int64 query(int l, int r) { return ask(r)-ask(l-1); }
}t[2];
int ans;
int main()
{
n = read();
for(int i = 1; i <= n; ++i) sum[i] = sum[i-1]+read();
for(int k = 0; (1<<k) <= sum[n]; ++k)
{
m = (1<<k)-1; int64 p = 0;
t[0].clear(); t[1].clear();
for(int i = 0; i <= n; ++i)
{
int c = (sum[i]>>k&1), d = (sum[i]&m);
p += t[c^1].query(0, d)+t[c^0].query(d+1, m);
t[c].add(d);
}
ans += (1<<k)*(p%2);
}
printf("%d\n", ans);
return 0;
}
|