校内模拟赛 T1 美好的每一天~不连续的异或

题目描述

简要题意：给定一个长度为 $n$ 的序列 $a_i$，求 $\sum_{i=1}^n\sum_{j=i+1}^{n}cnt_{a_i\oplus a_j}$，其中 $cnt_x$ 表示 $x$ 的二进制表示下 $1$ 的个数， $\oplus$ 表示异或

$n\le 36666666,a_i\le 2^{64}-1$

Solution

首先容易得到 $O(n\log n)$ 的做法，即我们对于每一位统计 $0$ 和 $1$ 的数量 $s$ 和 $t$，这一位的贡献就是 $s\times t$

类比这个做法，我们一次枚举 $w$ 位，然后记录这 $w$ 位的结果，最后 $O(\frac{64}{w}(2^w)^2)$ 统计答案即可，时间复杂度为 $O(\frac{64}{w}(n+2^{2w}))$，取 $w = 8$ 即可通过此题

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#define ll long long
#define ull unsigned long long
using namespace std;

int n, cnt[8][256];

ull seed;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> seed; std::mt19937_64 rng(seed);
    ll ans = 0; int N = 8, M = 255;
    for (int i = 1; i <= n; i++) {
        ull x = rng();
        for (int o = 0; o < N; ++o) ++cnt[o][x & M], x >>= N; 
    }
    for (int o = 0; o < N; ++o)
        for (int i = 0; i <= M; ++i)
            for (int j = i + 1; j <= M; ++j)
                ans += 1ll * cnt[o][i] * cnt[o][j] * __builtin_popcount(i ^ j);
    cout << ans << "\n";
    return 0;
}