[CF1466E] Apollo versus Pan

[CF1466E] Apollo versus Pan

Description

给定包含 (n) 个元素的序列 (X=[x_1,x_2,...,x_n])，求 (sum_{i=1}^{n}sum_{j=1}^{n}sum_{k=1}^{n}(x_i operatorname{and} x_j) imes(x_j operatorname{or} x_k))

Solution

枚举 j，把 i,k 分开考虑

拆位，对一位考虑，那么 xi and xj，在 xj=0 时就是 0，xj=1 时就是 xi=1 的个数，or 同理

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

#define int long long

const int mod = 1e9 + 7;

void solve()
{
    int n;
    cin >> n;

    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int ans = 0;

    int c1[66];
    memset(c1, 0, sizeof c1);
    for (int b = 62; b >= 0; b--)
    {
        for (int i = 1; i <= n; i++)
            if ((a[i] >> b) & 1)
                ++c1[b];
    }

    for (int j = 1; j <= n; j++)
    {
        int t1 = 0, t2 = 0;
        for (int b = 62; b >= 0; b--)
        {
            if ((a[j] >> b) & 1)
            {
                t1 += (1ll << b) % mod * c1[b] % mod;
                t2 += (1ll << b) % mod * n % mod;
            }
            else
            {
                t1 += 0;
                t2 += (1ll << b) % mod * c1[b] % mod;
            }
            t1 %= mod;
            t2 %= mod;
        }
        ans += t1 * t2 % mod;
        ans %= mod;
    }

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--)
        solve();
}