【ABC147】D - Xor Sum 4

atcoder.jp

解法

問題文通り実装してもO(N²)で間に合わない。

XOR演算を繰り返すため、ビットごとに考えたくなる。
そこで位ごとに、ビットが立っているかどうかをA[i]すべてで調べ、いくつビットが立っているかを計算することにする。
A[i] ≦ 2⁶⁰ なので、60の長さの配列を準備しておけば良い。
この配列をbit_cntと呼ぶことにする。

この計算ができたら、A[i]のjビット目が答えにどれだけ影響を与えるかを計算していく。
具体的には、

• A[i]のjビット目が立っている場合
  • jビット目が立っていない要素が他にいくつあるかを考える
  • N - bit_cnt[j]がそれに該当するが、既に見た要素も含まれているのでiを引いておく(重複して計算するのを回避するため)
  • つまり、2^j * (N - i - bit_cnt[j])を答えに加算する
  • bit_cnt[j]を一つ減らす
• A[i]のjビット目が立っていない場合
  • jビット目が立っている要素が他にいくつあるかを考える
  • それは、bit_cnt[j]が該当する
  • つまり、2^j * bit_cnt[j] を答えに加算する

実装

modintを使うと実装が楽。

bit演算についてはこの記事がとても分かりやすい。

qiita.com

void solve(long long N, std::vector<long long> A){
    vector<int> bit_cnt(60, 0);
    REP (i, N) {
        REP (j, 60) {
            // A[i]のjビット目が立っている場合
            // bit_cnt[j]に加算
            if (A[i] & (1LL << j)) bit_cnt[j]++;
        }
    }

    mint ans = 0;
    REP (i, N) {
        REP (j, 60) {
            mint n = (1LL << j);
            // A[i]のjビット目が立っている場合
            if (A[i] &  (1LL << j)) {
                ans += n * (N - i - bit_cnt[j]);
                bit_cnt[j]--;
            } else {
                ans += n * bit_cnt[j];
            }
        }
    }

    cout << ans << endl;
}```