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)になる。