题目链接：https://codeforc.es/contest/1466/problem/E
Only a few know that Pan and Apollo weren’t only battling for the title of the GOAT musician. A few millenniums later, they also challenged each other in math (or rather in fast calculations). The task they got to solve is the following:
Let x1,x2,…,xn be the sequence of n non-negative integers. Find this value:
∑i=1n∑j=1n∑k=1n(xi&xj)?(xj|xk)
Here & denotes the bitwise and, and | denotes the bitwise or.
Pan and Apollo could solve this in a few seconds. Can you do it too? For convenience, find the answer modulo 109+7.
Input
The first line of the input contains a single integer t (1≤t≤1000) denoting the number of test cases, then t test cases follow.
The first line of each test case consists of a single integer n (1≤n≤5?105), the length of the sequence. The second one contains n non-negative integers x1,x2,…,xn (0≤xi<260), elements of the sequence.
The sum of n over all test cases will not exceed 5?105.
Output
Print t lines. The i-th line should contain the answer to the i-th text case.
Example
input
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
output
128
91
1600
505
0
1
502811676
264880351
分析
对于每一项 xj ，可以按位算出 xj 对于所有项的与的累加以及对于所有项的或的累加，两者相乘就是这一项的答案，遍历 j 从 1 到 n 即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const ll mod = 1e9+7;
int t,n;
ll x[500007],sum[65],se[500007];
bool b[500007][65];void getb(int id,ll xx)
{
for(int i=0;i<=60;i++){
b[id][i] = 0;if((1ll << i) & xx){
b[id][i] = 1;sum[i]++;}}
}int main()
{
scanf("%d",&t);while(t--){
ll ans = 0;memset(sum,0,sizeof(sum));scanf("%d",&n);for(int i=1;i<=n;i++){
scanf("%lld",&x[i]);getb(i, x[i]);}for(int i=1;i<=n;i++){
se[i] = 0;for(int j=0;j<=60;j++){
if(b[i][j] == 1) continue;else se[i] = (se[i] + (1ll << j) % mod * sum[j] % mod) % mod;}se[i] = (se[i] + x[i] % mod * n % mod) % mod;}for(int i=1;i<=n;i++){
for(int j=0;j<=60;j++){
if(b[i][j] == 1) ans = (ans + (1ll << j) % mod * sum[j] % mod * se[i] % mod) % mod;}}printf("%lld\n",ans);}return 0;
}