题意：
给出(n,nleq 4cdot 10^5)个数，每个数(a_ileq 10^7)。
现要求：
[(a_1+a_2)oplus(a_1+a_3)oplus(a_1+a_n)oplus(a_2+a_3)opluscdotsoplus(a_{n-1}+a_{n})
]
其中(oplus)为异或和。
思路：
我们可以想到按位进行考虑，但进位不好处理。
假设我们考虑到第(k)位时，我们接下来求多少对数他们加起来在这一二进制位上面为(1)。
- 令(T=2^k)，从数值方面考虑，就是在这一位上为(1)，也就是说要不小于(T)。
- 因为每一位单独考虑，我们令(a_i=a_i\% (2T))，那么就消掉了高位。
- 结合第一点，我们要求的就是(Tleq a_i+a_j<2T)或(3Tleq a_i+a_j<4T)的对数。
- 那么枚举每一个数，然后对应二分一下即可。
按位进行考虑，并且消除高位的影响通过值来求解，是一种比较常见的套路。
时间复杂度为(O(nlog^2n))。
代码如下：
/*
* Author: heyuhhh
* Created Time: 2020/3/7 20:20:27
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 4e5 + 5;
int n;
int a[N], b[N];
void run() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int ans = 0;
for(int k = 24; k >= 0; k--) {
int T = 1 << k, cnt = 0;
for(int i = 1; i <= n; i++) b[i] = a[i] % (T << 1);
sort(b + 1, b + n + 1);
for(int i = 1; i <= n; i++) {
int p1 = lower_bound(b + i + 1, b + n + 1, T - b[i]) - b;
int p2 = lower_bound(b + i + 1, b + n + 1, 2 * T - b[i]) - b;
cnt += p2 - p1;
p1 = lower_bound(b + i + 1, b + n + 1, 3 * T - b[i]) - b;
p2 = lower_bound(b + i + 1, b + n + 1, 4 * T - b[i]) - b;
cnt += p2 - p1;
}
if(cnt & 1) ans += (1 << k);
}
cout << ans << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}
上面的代码中使用了二分，其实我们也可以不用二分。
我们维护一个前缀和，那么枚举每一位时可以直接通过前缀和来求解。
注意一下如果将自己算上时要把自身的贡献减去。
这种写法还是有些细节，尤其是边界这些。
细节见代码：
/*
* Author: heyuhhh
* Created Time: 2020/3/8 10:52:04
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '
'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ' '; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 4e5 + 5, M = 26;
int n;
int a[N], b[N];
int sum[1 << M];
void run() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int ans = 0;
for(int high = 2, k = 0; high < 1 << M; high <<= 1, ++k) {
for(int i = 0; i < high; i++) sum[i] = 0;
for(int i = 1; i <= n; i++) {
if(a[i] >> k & 1) b[i] |= (1 << k);
++sum[b[i]];
}
for(int i = 1; i < high; i++) sum[i] += sum[i - 1];
ll cnt = 0;
//if(k < 2) for(int i = 1; i <= n; i++) cout << b[i] << ' '; cout << '
';
//if(k < 2) for(int i = 0; i <= 3; i++) cout << sum[i] << ' '; cout << '
';
int T = 1 << k;
for(int i = 1; i <= n; i++) {
cnt += sum[2 * T - 1 - b[i]];
if(T - 1 - b[i] >= 0) cnt -= sum[T - 1 - b[i]];
cnt += sum[min(high - 1, 4 * T - 1 - b[i])] - sum[min(high - 1, 3 * T - 1 - b[i])];
if((b[i] << 1) >= T && (b[i] << 1) < 2 * T) --cnt;
if((b[i] << 1) >= 3 * T && (b[i] << 1) < 4 * T) --cnt;
}
//dbg(k, cnt);
cnt >>= 1;
if(cnt & 1) ans += 1 << k;
}
cout << ans << '
';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}