AcWing 5001. 异或和之和
原题链接
困难
作者:
Type-umr
,
2024-04-07 22:31:00
,
所有人可见
,
阅读 17
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int arr[N];
int pre[N];
int n;
//该题考察拆位和贡献法
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] ^ arr[i];
//异或的自反性,类似前缀和,一段区间异或可以表示为pre[r]^pre[l-1]
//异或可以按位独立运算,所以可以将n个数的每一个二进制位通过0、1来表示
//若一个二进制位上1为奇数则异或为1,1为偶数则异或为0(0异或任何数都是0,不考虑)
//故可以在异或前缀和的基础上求每个二进制位上的贡献对应的值
//因为只有0和1异或才能等于1,意味着有贡献度,所以遍历1到n所有数的每个二进制位
//记录二进制位上的0和1的个数,若当前数为1则加上前面的所有0个数,若当前数为0则加上前面的所以1个数,且c0++||c1++
//求得每一个二进制位上的sum值,乘以当前二进制表示的1<<i(2的i次方)即可
ll ans = 0;
for (int i = 20; i >= 0; i--) {
ll sum = 0;
int c0 = 1, c1 = 0;
for (int j = 1; j <= n; j++) {
if (pre[j] >> i & 1) {
sum += c0;
c1++;
}
else {
sum += c1;
c0++;
}
}
ans += sum * (1 << i);
}
cout << ans << endl;
return 0;
}