题意:给定一个长度为n的数组,求 以样例1为例子
会发实际在只要每次算第i位最后得出来的数字乘以2的i次方即可。最多32位撑死了。
cnt[0] 统计到目前为止出现的前缀异或结果为0的次数。
cnt[1] 统计到目前为止出现的前缀异或结果为1的次数。
用an记录异或为1的个数,直接加上s^1的个数就好啦
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N=2e5+10;
- ll a[N],s[N],n,cnt[3];
- ll f(int x){
- for(int i=1;i<=n;i++)s[i]=(a[i]>>x)&1;//x每位的值存入s
- for(int i=1;i<=n;i++)s[i]^=s[i-1];//前缀异或结果
- for(int i=0;i<=1;i++)cnt[i]=0;
- ll an=0;
- for(int i=1;i<=n;i++){
- an+=cnt[s[i]^1];//s[i]^1取反
- cnt[s[i-1]]++;
- }
- return an;
- }
- int main(){
- cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
- ll ans=0;
- for(int i=0;i<=31;i++)ans+=f(i)<<i;//2的i次方就是<<i
- cout<<ans<<endl;
- }
复制代码
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |