题目描述
给出n个数,计算$\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n(x_i\&x_j)×(x_j|x_k)$.
输入
第一行T组数据。
每组数据第一行一个n,第二行n个数$x_i$。$1<=n<=5·10^5$ ,$0<=x_i<2^{60}$
输出
公式的值。
样例
输入
8
2
1 7
3
1 2 4
4
5 5 5 5
5
6 2 2 1 0
1
0
1
1
6
1 12 123 1234 12345 123456
5
536870912 536870911 1152921504606846975 1152921504606846974 1152921504606846973
输出
128
91
1600
505
0
1
502811676
264880351
思路
(推公式) $O(n*C)$
$\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n(x_i\&x_j)×(x_j|x_k)$
$=\sum_{j=1}^n\sum_{i=1}^n\sum_{k=1}^n(x_i\&x_j)×(x_j|x_k)$
$=\sum_{j=1}^n \begin{bmatrix} \sum_{i=1}^n(x_i\&x_j)×\sum_{k=1}^n(x_j|x_k)\end{bmatrix}$
$=\sum_{j=1}^n F(j)×G(j)$
因为$0<=x_i<2^{60}$,我们可以用数组维护n个数二进制每一位的值,空间为n*60。
遍历第一维j,对于第二维i与k的累加,我们不可以遍历i、k,而是遍历60个二进制位(需与处理)。
F()函数如果$x_j$的二进制位为1,则加上该二进制位为1的数的数量 乘上该二进制。
G()函数如果$x_j$的二进制位为1,则加上二进制*n,为0则该二进制位为1的数的数量 乘上该二进制。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD=1e9+7;
const int Mn=5e5+17;
ll x[Mn],cnt[Mn][61],n;
ll F(int pos){
ll ret=0;
for(int i=0;i<=60;++i){
if(cnt[pos][i]) ret=((1ll<<i)%MOD*cnt[0][i]%MOD+ret)%MOD;
}
return ret;
}
ll G(int pos){
ll ret=0;
for(int i=0;i<=60;++i){
if(cnt[pos][i]) ret=((1ll<<i)%MOD*n%MOD+ret)%MOD;
else ret=((1ll<<i)%MOD*cnt[0][i]%MOD+ret)%MOD;
}
return ret;
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%lld",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&x[i]);
}
for(int j=0;j<=60;++j){
ll num=0;
for(int i=1;i<=n;++i){
if(x[i]&(1ll<<j)) cnt[i][j]=1,++num;
else cnt[i][j]=0;
}
cnt[0][j]=num;
}
ll ans=0;
for(int j=1;j<=n;++j){
ans=(F(j)*G(j)%MOD+ans)%MOD;
}
printf("%lld\n",ans);
}
}
推式子能力太弱了5555