Apollo versus Pan

Created by LXC on Sun Sep 17 21:47:55 2023

https://codeforces.com/problemset/problem/1466/E

ranting: 1800

tag: bitmasks, brute force, math

problem

给出$x_1, x_2, \ldots, x_n$

求$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n (x_i , & , x_j) \cdot (x_j , | , x_k)$

solution

$$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n (x_i , & , x_j) \cdot (x_j , | , x_k) = \sum_{j=1}^n \sum_{i=1}^n (x_i , & , x_j) \sum_{k=1}^n (x_j , | , x_k) = \sum_{j=1}^n \left[ \sum_{i=1}^n (x_i , & , x_j) \right] \cdot \left[ \sum_{k=1}^n (x_j , | , x_k) \right]$$

$f(x, c)$为x的二进制第c位的值。

$$\sum_i (x_i , & , x_j) = \sum_{c = 0}^{M} 2^c \sum_i f(x_i, c) \cdot f(x_j, c) = \sum_{c = 0}^{M} 2^c f(x_j, c) \sum_i f(x_i, c)$$

$$\sum_k (x_j , | , x_k) = \sum_{c = 0}^{M} 2^c \sum_k 1 - (1 - f(x_j, c)) \cdot (1 - f(x_k, c)) = \sum_{c = 0}^{M} 2^c \left[ n - (1 - f(x_j, c)) \sum_k (1 - f(x_k, c)) \right]$$

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 1000000007
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& i : a)
        cin >> i;
    vector<int> sf(61);
    for (int j = 0; j <= 60; j++) {
        for (ll i : a) {
            sf[j] += (i >> j & 1);
        }
    }
    // f(x, c) = x>>c&1
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll p = 1, x = 0, y = 0;
        for (int j = 0; j <= 60; j++) {
            ll b = a[i] >> j & 1;
            x += p * b % MOD * sf[j] % MOD;
            x %= MOD;
            y += p * (n - (1 - b) * (n - sf[j]) % MOD) % MOD;
            y %= MOD;
            p *= 2;
            p %= MOD;
        }
        ans += x * y % MOD;
        ans %= MOD;
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}