【题解】AtCoder Beginner Contest 147: D - Xor sum4
作者:
Alier
,
2019-12-21 15:13:19
,
所有人可见
,
阅读 833
题目点这里
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=300010,mod=1e9+7;
long long ans=0;
int main(){
int n;
cin>>n;
vector<long long> a(n);
for(int i=0;i<n;i++) cin>>a[i];
//位运算每一位互不影响,同一位可以一起算
//只有1与0进行异或时才得到1,因此这一位上1的数目乘0的数目就是异或为1的所有可能情况数
for(int i=0;i<60;i++){
long long x=0;
for(int j=0;j<n;j++) if(a[j]>>i &1 ) x++;//统计每个数第i位的1
long long now = x*(n-x) %mod;//每个数第i位的1的个数乘0的个数
for(int j=0;j<i;j++) now = now*2%mod;//把权重移回去
ans += now;
ans %=mod;
}
cout<<ans<<endl;
return 0;
}