A18254. 总异或和
填空题
较难
知识点
题目描述
总异或和
题目描述
给定长度为 n 的序列 A1,A2,,,,,An。
我们要计算所有数对 (i,j) 对应的 Ai + Aj 的总异或和。
即把所有满足 1 ≤ i,j ≤ n 的 Ai + Aj 依次进行异或，输出最终结果。
举例：当 n=3 时，计算式为
(A1+A1) ⊕ (A1+A2) ⊕ (A1+A3) ⊕
(A2+A1) ⊕ (A2+A2) ⊕ (A2+A3) ⊕
(A3+A1) ⊕ (A3+A2) ⊕ (A3+A3)
其中 ⊕ 表示按位异或运算。
输入格式
共两行：
第一行：一个正整数 n
第二行：n 个正整数，表示序列 A1,A2,,,,An
输出格式
输出一个整数，表示所有数对计算后的总异或值。
输入样例
3
2 12 27输出样例
42说明提示
1 ≤ n ≤ 106，1 ≤ Ai ≤ 109
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
ll ans = 0;
// 遍历每一位 0~30
for (int k = 0; k <= 30; ++k)
{
ll mod = 1LL << (k + 1);
ll half = 1LL << k;
vector<ll> rem;
for (ll x : a)
rem.push_back(x % mod);
sort(rem.begin(), rem.end());
ll cnt = 0;
int l = 0, r = n - 1;
// 统计 r_i + r_j >= half 且 < mod
for (; r >= 0; --r)
{
while (l < n && rem[l] + rem[r] < half)
l++;
cnt += n - max(l, r + 1);
}
// 统计 r_i + r_j >= mod + half
l = 0, r = n - 1;
for (; r >= 0; --r)
{
while (l < n && rem[l] + rem[r] < mod + half)
l++;
cnt += n - max(l, r + 1);
}
if (cnt % 2 == 1)
ans |= half;
}
cout << ans << endl;
return 0;
}
上一题
下一题