$$
\begin{aligned}
\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{k=1}^{n}\left(x_{i} \& x_{j}\right) *\left(x_{j} \mid x_{k}\right)
\end{aligned}
$$
$$
\begin{aligned}
=\sum_{i=1}^{n} \sum_{j=1}^{n}\left(x_{i} \& x_{j}\right) * \sum_{k=1}^{n}\left(x_{j} \mid x_{k}\right) \
\end{aligned}
$$
$$
\begin{aligned}
=\sum_{j=1}^{n}\left(\sum_{i=1}^{n}\left(x_{i} \& x_{j}\right) * \sum_{k=1}^{n}\left(x_{j} \mid x_{k}\right)\right) \
\end{aligned}
$$
$$
=\sum_{j=1}^{n} f(j) * g(j)
$$

(输入较大, 用scanf, cin超时)

这个题要将一个数字按位考虑, $ 10 = 1010 = 1_2^3 + 0_2^3 + 1_2^1 + 0_2^0 $

先分析这两个函数(f(j)和g(j)),
对于f(j)函数:
当x[j]的某一个位置为0的时候, 我们只需要统计有多少个x which 这个位置也是1. 因为1 & 1 = 1, 不然就是0
对于g(j)函数:
当x[j]的某一个位置为0的时候, 我们只需要统计有多少个x which 这个位置也是1. 因为1 | 0 = 1, 不然就是0
当x[j]的某一个位置为1的时候, 我们无需统计, 因为所有的都满足, 因为0 | 1 = 1, 并且1 | 1 = 1.

综上所述, 结果是1的位置相加就行了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;
#define rep(i, a, b) for(int i = a ; i <= b ; i++)

ll x[500010];
ll cnt[61];

int main() {
    int t;
    cin >> t;
    int n;
    while (t--) {
        cin >> n;
        memset(cnt, 0, sizeof cnt);

        rep(i, 1, n) {
            scanf("%lld", &x[i]);
            rep(j, 0, 59) {
                cnt[j] += ((x[i] >> j) & 1);
            }
        }
        ll ans = 0;
        
        rep (j, 1, n) {
            ll J, G;
            J = G = 0;
            rep(k, 0, 59) {
                if ((x[j] >> k) & 1) {
                    J += cnt[k] % mod * ((1LL << k) % mod) % mod;
                    J %= mod;
                    G += n      % mod * ((1LL << k) % mod) % mod;
                    G %= mod;
                }
                else {
                    G += cnt[k] % mod * ((1LL << k) % mod) % mod;
                    G %= mod;
                }
            }
            ans += J * G % mod;
            ans %= mod;
        }
        //cout << "                ";
        printf("%lld\n", ans);
        //cout << ans << '\n';
    }
    return 0;
}