[蓝桥杯 2023 省 A] 异或和之和

题目来自洛谷网站：

暴力思路：

先进性预处理，找到每个点位置的前缀异或和，在枚举区间。

暴力代码：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5+20;int n;
int arr[N], ls[N];//前缀异或和数组 lssigned main(){cin >> n;for(int i = 1; i <= n; i++) cin >> arr[i];//预处理-前缀异或和for(int i = 1; i <= n; i++){ls[i] = ls[i-1] ^ arr[i];}//枚举数组int ans = 0;for(int i = 0; i < n; i++){for(int j = i+1; j <= n; j++){//得到i-j这一段的异或和ans += ls[i] ^ ls[j];}}cout << ans << endl;return 0;
}

 拆位+贡献法优化：

①将数组A数转换为二进制来计算，二进制中每一位计算’互不影响‘。

②题目中Ai最大为2^20，我们从20开始枚举到0，按顺序取出数组Ai的第 i 位，对数组中每个数第 i 位计算值，累加起来。

③对于每个数的第 i 为，只有1、0两种情况，对 i 位判断奇偶性。我们用 s 来存 i ，s 就相当于每个数第 i 位的前缀和。再用 ji 来记录每个数中是奇数的数量，用 ou 来记录每个数中是偶数数量。同时，ou 初始化为1，ji 初始化为0。

④如果 s 为偶数，这个区间异或为0，我们要避免这种情况。因此 s 为奇数的时，这个大的区间总共有 ou 个区间异或结果为1。s 为偶数时，总共有 ji 个区间异或结果为1。由于 i 第几位是确定的，所以每个区间的值是确定的。对于 s 奇数，用 ans += （1 << i）* ou；对于 s 为偶数，直接ans += （1 << i）* ji。

拆位+贡献法代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+20;int n;
int arr[N];signed main(){cin >> n;for(int i = 1; i <= n; i++){cin >> arr[i];}//拆分int ans = 0;for(int i = 20; i >= 0; i--){//表示接下来枚举元素位置j 前面有多少1、0int ji = 0, ou = 1;//表示接下来枚举元素位置j是奇数还是偶数int s = 0;for(int j = 1; j <= n; j++){//得到arr[j]二进制“第一位” 并判断奇数偶数int k = arr[j] >> i & 1;s += k;//奇数if(s % 2){ans += (1 << i) * ou;ji += 1;}//偶数else{ans += (1 << i) * ji;ou += 1;}}}cout << ans << endl;return 0;
}