notepad.exe

つまり覚え書き

ARC098/ABC098 D - Xor Sum 2

復習日記

問題ページ

問題概要

  • 長さ Nの整数列 Aが与えられる
  •  A_l xor A_{l+1} xor ... xor A_r = A_l + A_{l+1} + ... + A_rを満たす (l, r)の組の個数を求める

考え方

サンプルを見てみると、

  •  2 = 0 0 1 0
  •  5 = 0 1 0 1
  •  4 = 0 1 0 0
  •  6 = 0 1 1 0

となっていて、 (l, r) = (1, 2)の時にちょうど1の位置がお互いに干渉していないことがわかります。 例えば、1がどこかの桁に2つ以上あるときに xorをとると0になってしまいますが、加算をすると繰り上がって1の位置がずれてしまいます。
ということは、区間のすべての桁について1の個数が1個または0個になるような区間を求めれば答えを求めることができることがわかります。

というのが解説にもありますが、区間を尺取りで実際に計算しながら求めれば答えを求めるのには十分です。

提出コード

数える実装が上手くきれいに書けなくてサンプルがなかなか通らなかったです。 結局右側を順番に回して左側を詰めていく実装に落ち着きました。 あとほかの人の実装が頭よかったので参考にしました。