7K12 blog

猫でも分かる何か

ABC147 D - Xor Sum 4

f:id:tkr987:20200718225812p:plain
https://atcoder.jp/contests/abc147/submissions/13626753

https://atcoder.jp/contests/abc147/submissions/15303781

「集合nと集合mの片道は全部でn×m個」＝「完全二部グラフ」＝「辺の数はn×m個」

f:id:tkr987:20200718222338p:plain

制約から $O(N^2)$ が許されないので、ビット桁ごとに処理して計算量削減を目指す。XOR演算なので $A_i$ と $A_j$ をビット毎に分解したとき、片方0で片方1なら加算される。よって、 $A_i$ を決め打ちしてd桁目ビットが1、 $A_{i+1}$ から $A_N$ までのd桁目ビット0の個数がpだったとき、 $p \times 2^d$ だけ加算されていく。 $A_{i+1}$ から $A_{N}$ のd桁目ビット値の個数は累積和にすれば $O(1)$ になるので、最終的に計算量が $O(N log N)$ になる。 $A_i$ を決め打ちしてd桁目ビットが0のときも同様。

ただし、上記実装は面倒なので更に工夫したい。「集合nと集合mの片道本数」と「完全二部グラフの辺の本数」が同値なことに気づくことが出来れば、そもそも $A_i$ を決め打ちする必要がない。 $A_1$ から $A_N$ におけるd桁目のビット0の個数をp、ビット1の個数をq、とするとd桁目の合計は $2^d \times pq$ になる。計算量は $O(N \log N)$ になる。