Xor Sigma Problem
Xor Sigma Problem
首先可以转化成前缀异或和去考虑,那么也就是求任意两个前缀异或和相加的值,可以一位位的来求,每位最后的答案即是0和1出现次数的乘积。
代码:
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5+5;
int n;
int pre[N];
int a[N];
int g[N][5];void solve(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)pre[i] = pre[i-1] ^ a[i];int ans = 0;for(int i=0;i<=32;i++)g[i][0] ++;for(int i=1;i<=n;i++){for(int j=0;j<=32;j++){ans += g[j][bool(pre[i]&(1LL<<j))^1]*(1LL<<j);}for(int j=0;j<=32;j++){g[j][bool(pre[i]&(1LL<<j))]++;}}for(int i=1;i<=n;i++)ans -= a[i];cout<<ans<<"\n";}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T=1;while(T--){solve();}return 0;
}