题意:
给定长度为 \(n\) 的序列 \(x\)。
求
想法:
-
首先进行化简:
.\(\sum^{n}_{i=1} \sum^{n}_{j=1} \sum^{n}_{k=1} (x_{i}\ \& \ x_{j})\times (x_{j}\ |\ x_{k})\text{}\)
.\(\Longrightarrow \sum^{n}_{j=1} \sum^{n}_{i=1} \sum^{n}_{k=1} (x_{i}\ \& \ x_{j})\times (x_{j}\ |\ x_{k})\text{}\)
.\(\Longrightarrow \sum^{n}_{j=1} (\sum^{n}_{i=1} (x_{i\ }\& \ x_{j}))\times (\sum^{n}_{k=1} (x_{j}\ |\ x_{k})\text{} )\) -
从上面的式子中看得出来 \(j\) 是一定要枚举的,显然复杂度应该是不能是 \(O(n^2)\),那么可以想到枚举二进制位,也就是把 \(x_{i}\ \& \ x_{j}\) 的值通过对二进制位上拥有 \(1\) 的个数求出答案,因为 $x_{i}<2^{60} $,那么复杂度可以做到 \(O(60\times n)\)。
-
我们可以预处理出整个序列在某一位上 \(1\) 的个数,从而避免对 \(i,k\) 的枚举。
-
对 \(x_{i}\ \& \ x_{j}\),是这两个数某一位上都为 \(1\),最后答案才能加上这位 \(1\) 的贡献,\(x_{i}\ |\ x_{j}\) 只有有 \(1\) 即可加上贡献。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int maxn=500005;
ll x[maxn];
ll cnt[105];
int main()
{
int T,n;
cin>>T;
while(T--){
memset(cnt,0,sizeof cnt);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&x[i]);
for(int j=0;j<=60;j++){
if((1ll<<j)&x[i])cnt[j]++;
}
}
ll ans=0;
for(int i=1;i<=n;i++){
ll base=1;
ll num1=0,num2=0;
for(int j=0;j<=60;j++){
if((1ll<<j)&x[i]){
num1=(num1+base*cnt[j]%mod)%mod;
num2=(num2+base*n%mod)%mod;
}else{
num2=(num2+base*cnt[j]%mod)%mod;
}
base=base*2%mod;
}
ans=(ans+num1*num2%mod)%mod;
}
cout<<ans<<endl;
}
return 0;
}