Good Bye 2020 E

大意

给定 \(N\) 和 \(N\) 个数 \(x_1,x_2,...,x_n\) ，

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

思路

说实话这种题第一时间应该想到位运算...我还是太菜了...

考虑一步简单变形 \(\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]\)

然后我们想办法 \(\Theta(log)\) 统计方括号中的式子。

对于固定的 \(x_j\) ，\(\sum_{i=1}^n (x_i \, \& \, x_j)\) 的值就是 \(x_j\) 在二进制下的每一位，分别与 \(x_1,...,x_n\) 做 与 运算的值的累加。

更简单地说，就是 \(x_j\) 在二进制下的每一位，与 \(x_1,...,x_n\) 在二进制下相同的位数做 与 运算的值的累加。

对于 \(x_j\) 为 \(1\) 的位，答案显然就是 \(x_1,...,x_n\) 在二进制相同的位数为 \(1\) 的个数乘以此位代表的 \(2\) 的次幂的值的累加 。

对于 \(x_j\) 为 \(0\) ，显然为 \(0\)

这样对于 \(j\) ，我们在 \(logx_j\) 的时间内求出了答案。

对于 \(\sum_{k=1}^n (x_j \, | \, x_k)\) ，方法类似。

总之，复杂度为 \(\Theta(Nlog(max(x_i)))\)

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

#define ll long long
#define ull unsigned long long
#define cint const int&
#define Pi acos(-1)

const int mod = 1e9+7;
const int inf_int = 0x7fffffff;
const ll inf_ll = 0x7fffffffffffffff;
const double ept = 1e-9;

int t, n, mx;
ll num[62];
ll a[500500];

void deal(ll x) {
    int cnt=0;
    while(x) {
        if(x&1) ++num[cnt];
        x >>= 1;
        ++cnt;
    }
    mx = max(mx, cnt);
}

inline ll sol_1(ll x) {
    int cnt=0;
    ll tmp = 0;
    while(x && cnt <= mx) {
        if(x&1) {
            tmp = (tmp + ((1ll<<cnt)%mod*num[cnt]) % mod)%mod;
        }
        x >>= 1;
        ++cnt;
    }
    return tmp;
}

inline sol_2(ll x) {
    int cnt=0;
    ll tmp = 0;
    while(cnt <= mx) {
        if(x&1) {
            tmp = (tmp + ((1ll<<cnt)%mod*n)%mod)%mod;
        } else tmp = (tmp + ((1ll<<cnt)%mod*num[cnt]) % mod)%mod;
        x >>= 1;
        ++cnt;
    }
    return tmp;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    ll t1, t2, ans;
    while(t--) {
        memset(num, 0, sizeof num);
        ans = mx = 0;
        cin >> n;
        for(int i=1; i<=n; i++) cin >> a[i], deal(a[i]);
        for(int i=1; i<=n; i++) {
            t1 = sol_1(a[i]);
            t2 = sol_2(a[i]);
            ans = (ans + (t1*t2)%mod) % mod;
        }
        cout << ans << endl;
    }
    return 0;
}

61min,-0

Good Bye 2020 E

原文：https://www.cnblogs.com/ullio/p/14216025.html