けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 147 D - Xor Sum 4 (水色, 400 点)

AtCoder AtCoder400点 ABC-D 数列 XOR 各要素について独立に考えてよい 各桁ごとに見る 解空間:O(N^2)通りの選択肢 総和を求める パリティ 水色diff

考え方自体は典型的ではある

問題へのリンク

問題概要

N 個の整数 A_{1}, \dots, A_{N} が与えられる。
これらから 2 個選んで XOR をとって得られる整数 ( \frac{N(N-1)}{2} 個ある) の総和を 1000000007 で割ったあまりを求めよ。

制約

  • 2 \le N \le 3 \times 10^{5}
  • 0 \le A_{i} \lt 2^{60}

考えたこと

XOR をみたら、とにかく「各桁ごとに考える」というのが定石ではある。その視点でいうと、問題は次のように考えることができる。

  • d 桁目について、
  • \frac{N(N-1)}{2} 個の値のうち、 d 桁目が 1 であるものの個数を a_{d} とする
  • このとき、答えには a_{d} \times 2^{d} を加算する

という風になる。

d 桁目が 1 である個数を求める

問題は「 \frac{N(N-1)}{2} 個の値のうち、 d 桁目が 1 であるものの個数 a_{d}」を求めることに帰着された。

XOR は「0 と 0 は 0」「1 と 1 は 0」「0 と 1 は 1」ということから、

  • A_{1}, \dots, A_{N} のうち、 d 桁目が 1 であるものの個数を p
  • A_{1}, \dots, A_{N} のうち、 d 桁目が 0 であるものの個数を q

としたとき、 pq 個となる。

まとめ

まとめると、

  • 各 d 桁目について
  • N 個の整数のうち、 d 桁目が 1 である個数は p、0 である個数を q として
  • pq \times 2^{d} を加算する

という風にして求めることができる。計算量は O(N\log{A})。

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

const int MOD = 1000000007;
int main() {
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    long long res = 0;
    long long two_factor = 1;
    for (int d = 0; d < 60; ++d) {
        long long even = 0, odd = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] & (1LL<<d)) ++odd;
            else ++even;
        }
        long long add = (odd * even) % MOD * two_factor % MOD;
        res = (res + add) % MOD;
        two_factor = (two_factor * 2) % MOD;
    }
    cout << res << endl;
}