# Nemlit 的博客

By a konjac

### 题解 P3760 【[TJOI2017]异或和】

posted on 2019-09-24 14:36:09 | under 题解 |

$$\sum_{k = 0} ^ {2 ^ k <= sum[n]}\ *\ ((\sum_{i = 1}^{n}\sum_{j = 1}^i(sum[i] - sum[j - 1]) >> k\ \&\ 1)\ \%\ 2)\ *\ 2 ^ k$$

$1.sum[j]_k = 0\ \&\&\ sum[j]_{1\ - \ k - 1} <= sum[i]_{1 - k - 1}$

$2.sum[j]_k = 1\ \&\&\ sum[j]_{1\ -\ k - 1} > sum[i]_{1\ -\ k - 1}$

$1.sum[j]_k = 1\ \&\&\ sum[j]_{1\ - \ k - 1} <= sum[i]_{1 - k - 1}$

$2.sum[j]_k = 0\ \&\&\ sum[j]_{1\ -\ k - 1} > sum[i]_{1\ -\ k - 1}$

# $Code:$

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
#define il inline
#define re register
#define int long long
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define mem(k, p) memset(k, p, sizeof(k))
#define lb(x) (x)&(-(x))
#define maxn 1000005
int n, m, a[maxn], sum[maxn], ma, Ans, ans;
struct Tree {
int t[maxn];
il void add(int u, int v, int x) {
while(u <= x) t[u] += v, u += lb(u);
}
il void Add(int u, int v, int x) {
add(u + 1, v, x + 1);
}
il int query(int u) {
int ans = 0;
while(u) ans += t[u], u -= lb(u);
return ans;
}
il int query(int l, int r) {
return query(r + 1) - query(l);
}
}A, B;//A表示0的树状数组，B表示1的
signed main() {
n = read();
rep(i, 1, n) a[i] = read(), sum[i] = sum[i - 1] + a[i], ma = max(ma, sum[i]);
for(re int k = 0; (1 << k) <= ma; ++ k) {
memset(A.t, 0, sizeof(A.t)), memset(B.t, 0, sizeof(B.t)), Ans = 0;
int pax = (1 << k) - 1;//我们只考虑1~k位
rep(i, 0, n) {
int temp = sum[i] & pax;//求出sum[i]_{1-k}
//cout << k << ' ' << temp << endl;
if((sum[i] >> k) & 1) {
Ans += A.query(0, temp) + B.query(temp + 1, pax), B.Add(temp, 1, pax);
}
else {
Ans += B.query(0, temp) + A.query(temp + 1, pax), A.Add(temp, 1, pax);
}
}
//cout << Ans << ' ' << ans << endl;
ans += (Ans % 2) * (1 << k);
}
printf("%lld", ans);
return 0;
}