AcWing 5001. 异或和之和 二进制拆位
原题链接
困难
作者:
jyyy
,
2024-02-05 18:38:14
,
所有人可见
,
阅读 131
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n;
int a[N];
int w[31][2];
//* acw5001 异或和之和
//* 题意:给定一个数组,求所有子段异或和的总和
//* 思路:
//* 由异或性质,作异或前缀和后
//* l-r 段异或和为 pre[l-1]^pre[r]
//* 前缀处理后仍只能达到 O(n^2) 而 n<=1e5
//* 这里考虑 将数拆为二进制 的思想来优化
//* 拆成二进制的目的在于
//* 二进制每一位只有 0/1 而只有 0^1=1 对答案有贡献
//* 且因为只有 0/1 我们很容易记录一段异或和每位上的情况
//* 从而得到思路 仍然前缀处理
//* 从前往后依次拆分前缀和 记录每一位的 0/1 个数
//* 比如处理到某前缀和的某位是 1
//* 那么这个 1 可以和 前面的前缀和中同位 的 0 产生贡献
//* 记前面有 cnt 个 0 位数是 t 则贡献 (1ll<<t)*cnt
//* 处理完前 i 个前缀和时 数组前 i 个元素构成的所有子段就处理好了
//* O(30n)
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
int ans=0;
for(int i=1;i<=n;i++)cin>>a[i],a[i]^=a[i-1];
for(int i=0;i<=n;i++){
//* 为什么要处理 a[0] ?
//* 因为处理了 pre[l-1]
//* 才能在处理 r 时得到 pre[l-1]^pre[r] 的贡献
//* 即处理了 a[0] 才能得到 1->i 子段的贡献
for(int t=0;t<=30;t++){
int f=(a[i]>>t)&1;//* 这一位是 0/1
w[t][f]++;//* 记录
ans+=(1ll<<t)*w[t][!f];//* 加上贡献
}
}
cout<<ans;
return 0;
}