异或和之和

//暴力做法 枚举每个子区间 O(n^3)
//优化1 利用前缀异或和快速求出区间异或和 O(n^2) 
//优化2 处理位运算的常用方法：拆位法  常用的思想：贡献法思想

下面详见优化2：

1.拆位贡献法 

2.实战真题1 

题目链接：1.异或和之和 - 蓝桥云课

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
	int n;
	cin>>n;
	vector<int>a(n);
	for(int i=0; i<n; i++)
	{
		cin>>a[i];
	}
	int result=0;
	for(int i=20; i>=0; i--) //遍历位数 
	{
		int s=0,n0=1,n1=0; //s表示前缀和，n0表示偶数个数（保证奇数本身占1），n1奇数个数 
		for(int j=0; j<n; j++)
		{
			int bit=(a[j]>>i)&1; //按位&，逐位判断0或1，计算贡献 
			s+=bit;  
			if(s%2) //奇数 
			{
				result+=(1<<i)*n0; //合法个数(2^n0)*合法区间 
				n1++;
			}
			else
			{
				result+=(1<<i)*n1;
				n0++;
			}
		}
	}
	cout<<result<<endl;
	return 0;
}

3.实战真题2 

初步掌握之和再练习一道题，题目链接： 19.区间异或的和 - 蓝桥云课

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
signed main()
{
	int n;
	cin>>n;
	vector<int>a(n);
	for(int i=0; i<n; i++)
	{
		cin>>a[i];
	}
	int result=0;
	for(int i=30; i>=0; i--) //遍历位数 
	{
		int s=0,n0=1,n1=0; //s表示前缀和，n0表示偶数个数（保证奇数本身占1），n1奇数个数 
		for(int j=0; j<n; j++)
		{
			int bit=(a[j]>>i)&1; //按位&，逐位判断0或1，计算贡献 
			s+=bit;  
			if(s%2) //奇数 
			{
				result+=((1<<i)*n0)%mod; //合法个数(2^n0)*合法区间 
				n1++;
			}
			else
			{
				result+=((1<<i)*n1)%mod;
				n0++;
			}
		}
	}
	cout<<result<<endl;
	return 0;
}