每日一题~ abc 365 E 异或运算（拆位+贡献）

处理位运算常用的方法：
拆位法（一位一位的处理，通常题目中会给出元素的最大是2的的多少次幂，当然也有给10的次幂的，自己注意一下就可以了）
常用的思想 ：
算贡献。
异或的性质：
A^A=0
A^0=A
异或 具有类似前缀和的性质。可以通过前缀异或 求区间的异或值

---

洛谷lqb
题意：对于一组数，求所有子串的异或和 之后求和
因为 异或的前缀和的性质。所以区间的异或值，可以表示为前缀的异或

通过转化，其实就是求，异或前缀数组，两两异或的 和。
我们 一位一位的考虑。
对于某一位来说 ，
假设前缀数组中的元素 这一位上的数字是：
0 0 1 0 1，考虑两两异或，只有 1 和 0 能产生一个1.
那么 这一位对答案的贡献是 0的个数*1的个数 *这一位的权重。
将每一位的贡献加起来。
最后不要忘记每一个B元素都要和0异或一下。这个从上面的数学公式中，可以看出来。这个对应的就是 一个前缀区间的异或值。体现在代码中，就是cnt0=1

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n;cin>>n;vector<int>a(n+1);for (int i=1;i<=n;i++)cin>>a[i],a[i]^=a[i-1];int ans=0;for(int i=0;i<=20;i++){int cnt1=0,cnt0=1;for (int j=1;j<=n;j++){if ((a[j]>>i )&1)cnt1++;else cnt0++;}ans+=cnt0*cnt1*(1<<i);}cout<<ans<<'\n';
}

abc 365 E
题意：根据 异或前缀的性质，可以转换一下。

乍一看，这个很像 B数组两两异或的和。但是我们可以注意到 并没有相邻两项的异或。两两异或的结果很好求。
我们只需要，对答案减去B相邻两项的异或。就可以了。
有一个的小细节：
B数组的最初的元素是B0，所以数组开到了n+1。用数学公式表示很清楚~~

#include <bits/stdc++.h>
using namespace std;
#define int long long 
void solve()
{int n;cin>>n;vector<int>a(n+1);for (int i=1;i<=n;i++)cin>>a[i],a[i]^=a[i-1]; int ans=0;for (int i=1;i<=n;i++)ans-=(a[i]^a[i-1]);for (int i=0;i<=30;i++){int cnt[2]{};for (int j=0;j<=n;j++){int x=(a[j]>>i) &1;cnt[x]++;}ans+=cnt[0]*cnt[1]*(1ll<<i);}cout<<ans<<"\n";}

添加链接描述
意外发现了，洛谷上的这个异或的题单。脑筋急转弯一下。
1，所有 子数组的元素和 的和。考虑每个元素的贡献，是包含这个元素的子数组的个数，
对于下标从1开始的情况，**包含这个元素的子数组的个数是（i）*（n-i+1).**累加起来就可以了。
2，求所有子数组的异或和 的异或和。因为X^X=0,所以只有子数组中出现奇数次的数字才会产生贡献。利用map来存储。

void solve()
{int n;cin>>n;map<int,int>mp;int t,tt;for (int i=0;i<n;i++){cin>>t;tt=(i+1)*(n-i);mp[t]+=tt;}int ans=0;for (auto [x,y]:mp){if (y&1){ans^=x;}}cout<<ans<<"\n";
}

3.所有子数组的异或和 的和。这道和上文第一题一样。
4.不会，先略过去
下面的题都是子序列
5.和1的子数组不同，这次是所有非空子序列的元素和 的元素和。
对于第i 个元素，包含这个元素的子序列有 2^(n-1),相当于剩下的元素都有选和不选两种选择。
所以将每个元素的贡献加起来就可以了
6.所有非空子序列的 异或和 的异或和。只有贡献奇数次的数值才会产生贡献。
每个数贡献的是 2^(n-1) 次，只有n=1的时候，是奇数。输出这个数值，就可以了。其他时候都是零。
7.计算非空子序列的 异或和 的和 。也是拆位思考。如果这一位没有1，那么贡献是0.如果有1那么贡献是2^(n-1) 再乘上权重。（不是很明白，怎么算的贡献）先贴上灵神的题解，日后再来想想。

8.计算 非空子序列 和的异或和。
考虑枚举累加每个子序列和的可能值的贡献
对当前序列数和sum，得到该和的方案数为奇数时贡献为sum，否则为0
考虑使用01背包推导序列数和的方案数的奇偶性
dp[j]表示装满j 的方案数。

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define int long long void solve()
{int n;cin>>n;vector<int>a(n);int sum=0;for (int i=0;i<n;i++){cin>>a[i];sum+=a[i];}vector<int>dp(sum+1);//装满容量为j的背包，有多少种方法dp[0]=1;for (int i=0;i<n;i++)for (int j=sum;j>=a[i];j--){dp[j]+=dp[j-a[i]];}int ans=0;for (int i=1;i<=sum;i++){if (dp[i]&1)ans^=i;}cout<<ans<<"\n";}