E - Xor Sigma Problem（abc365）

题意：给定一个长度为n的数组，求

以样例1为例子

会发实际在只要每次算第i位最后得出来的数字乘以2的i次方即可。最多32位撑死了。
cnt[0] 统计到目前为止出现的前缀异或结果为0的次数。
cnt[1] 统计到目前为止出现的前缀异或结果为1的次数。
用an记录异或为1的个数，直接加上s^1的个数就好啦

1. #include<bits/stdc++.h>
2. using namespace std;
3. typedef long long ll;
4. const int N=2e5+10;
5. ll a[N],s[N],n,cnt[3];
6. ll f(int x){
7.         for(int i=1;i<=n;i++)s[i]=(a[i]>>x)&1;//x每位的值存入s
8.         for(int i=1;i<=n;i++)s[i]^=s[i-1];//前缀异或结果
9.         for(int i=0;i<=1;i++)cnt[i]=0;
10.         ll an=0;
11.         for(int i=1;i<=n;i++){
12.                 an+=cnt[s[i]^1];//s[i]^1取反
13.                 cnt[s[i-1]]++;
14.         }
15.         return an;
16. }
17. int main(){
18.         cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
19.         ll ans=0;
20.         for(int i=0;i<=31;i++)ans+=f(i)<<i;//2的i次方就是<<i
21.         cout<<ans<<endl;
22. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。