Codeforces 1466E Apollo versus Pan

题意

给一个长度为$n(1\leq n\leq 5\cdot10^5)$的$x$数组，问

$\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k=1}^n(x_i\&x_j)\cdot(x_j|x_k) \mod 1e9+7$

分析

模拟是$n^3$，显然不现实。

对于位运算想到是否可以拆位，每一位独立的运算，独立的做出贡献，发现如果$x_j$的某一个为$1$，那么一定能做出贡献，考虑这一位能做出多少贡献。

手玩下数据可以发现，其他位会产生影响，所以独立拆位很难处理，但是给了我们启发，可以考虑通过枚举$x_j$，来获取答案，那么将公式化为$\sum\limits_{j=1}^n(\sum\limits_{i=1}^n(x_i\&x_j)\cdot\sum\limits_{k=1}^n(x_j|x_k))$。

考虑第一项和，对于$x_j$ 的第$y$位，如果该位是$1$，需要分别与$x_1,x_2,…,x_n$做$\&$运算，而如果$x_i$的该位是$1$，则第一项就要加上$1<<y$，那么我们可以考虑预处理所有数在某一位上的和，假设$sum[y]$表示所有数在第$y$位上做的贡献，那么如果$x_j$的第$y$位是$1$，第一个式子的和就要加上$sum[y]$。

同理考虑第二项和，对于$x_j$的第$y$位，如果该位是$1$，那么对于所有数其$|$运算，该位都能获得$1<<y$的值，所以和加上$(1<<y)*n$，而如果该位不是$1$，那么如果$x_k$的该位是$1$，则第二项和要加上$1<<y$，否则不需要，逻辑与上式相同，则加上$sum[y]$即可

最后乘起来即可，时间复杂度$O(60*n)$

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define repd(z, x, y) for(int z=x;z>=y;--z)
#define com bool operator<(const node &b)const
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int T = 1;
int a[maxn];
int sum[65];

void solve() {
    int n;
    cin >> n;
    rep(i, 0, 60)sum[i] = 0;
    int tot = 0;
    rep(i, 1, n) {
        cin >> a[i];
        tot = (tot + a[i]) % mod;
        rep(j, 0, 59) {
            if ((a[i] >> j) & 1) {
                sum[j] = ((1ll << j) % mod + sum[j]) % mod;
            }
        }
    }
    int ans = 0;
    rep(i, 1, n) {
        int toti = 0;
        rep(j, 0, 59) {
            if ((a[i] >> j) & 1) {
                toti = (toti + sum[j]) % mod;
            }
        }
        int totk = 0;
        rep(j, 0, 59) {
            if (!((a[i] >> j) & 1)) {
                totk = (totk + sum[j]) % mod;
            } else {
                totk = (totk + (1ll << j) % mod * n % mod) % mod;
            }
        }
        ans = (ans + toti * (totk) % mod) % mod;
    }
    cout << ans << '\n';
}

signed main() {
    start;
    cin >> T;
    while (T--)
        solve();
    return 0;
}