TechFUL: Xor Rush

TechFUL TechFUL: 中級 XOR

ABC147 の Xor Sum 4 と実質同じ問題．

問題概要

長さ N の整数列 A と長さ M の整数列 B が与えられる．

\displaystyle \sum_{i=0}^{N-1} \sum_{j=0}^{M-1} A_{i} \oplus B_{j} \tag{1} を求めよ．

問題のリンク

制約

  • 1 \leq N \leq 2 \times 10^{5}

  • 0 \leq A_{i}, B_{j} \leq 10^{6}

解法

XOR 系の問題なので A_{i}, B_{j} を2進数表示して、各桁ごとに考えてみる．

まず、 A_{i} \oplus B_{j} を2進数表示すると何桁になるか調べる．

これは、制約から 0 \leq A_{i}, B_{j} \leq 10^{6} より A_{i} \oplus B_{j} \leq 10^{6} \lt 2^{20}

となり、高々20桁と分かる．

次に、式 (1) を2進数表示を意識して式変形する．

\begin{align} \sum_{i=0}^{N-1} \sum_{j=0}^{M-1} A_{i} \oplus B_{j} &= \sum_{i=0}^{N-1} \sum_{j=0}^{M-1} \sum_{d=0}^{19} \lbrace (A_{i} の d 桁目) \oplus (B_{j} の d 桁目) \rbrace \times 2^{d} \\ &= \sum_{d=0}^{19} 2^{d} \sum_{i=0}^{N-1} \sum_{j=0}^{M-1} \lbrace (A_{i} の d 桁目) \oplus (B_{j} の d 桁目) \rbrace \\ &= \sum_{d=0}^{19} 2^{d} \left(cntA_{d, 0} \cdot cntB_{d, 1} + cntA_{d, 1} \cdot cntB_{d, 0} \right) \end{align} \tag{2}

ただし、 cntA_{d, b} を d ビット目が b \in \lbrace 0, 1\rbrace である A の要素の個数とする．

同様に cntB_{d, b} も定義する．

以上より、 cntA, cntB を計算すれば、式 (2) を基に答えを得る．

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < M; ++i) cin >> B[i];

    long long cntA[20][2] = {}, cntB[20][2] = {};
    for (int d = 0; d < 20; ++d) {
        for (int i = 0; i < N; ++i) {
            cntA[d][A[i] >> d & 1]++;
        }
        for (int i = 0; i < M; ++i) {
            cntB[d][B[i] >> d & 1]++;
        }
    }

    long long ans = 0;
    for (int d = 0; d < 20; ++d) {
        ans += (1LL << d) * (cntA[d][0] * cntB[d][1] + cntA[d][1] * cntB[d][0]);
    }
    cout << ans << endl;
}