ARC 092 D - Two Sequences

• 問題

問題概要

N要素の数列{a_i}, {b_i} が与えられる.
Xor_(1<=i,j<=N) (a_i + b_i) を求めよ.

解法

a_i + b_j のkビット目の1の数の偶奇を考える.
x + y = ( x & y ) << 1 + ( x xor y ) から,
(a_i , b_j のkビット目の立っている数) * N + (k-1ビット以下からの桁上がり) の偶奇を考えれば良い.
前半はそのまま数えればよく, 後半は ((1<<k) - 1) でマスクして(kビット目以上を0にする)ソートし,
各a_iについて, b_j + a_i >= 2^k なるjの数をにぶたんで数えれば良い.
計算量はO(30NlogN)

メモ

こういうのは大体各ビットに注目すれば解ける(自戒)

コード