ARC098/ABC098 D - Xor Sum 2
復習日記
問題概要
- 長さの整数列が与えられる
- を満たすの組の個数を求める
考え方
サンプルを見てみると、
となっていて、の時にちょうど1の位置がお互いに干渉していないことがわかります。
例えば、1がどこかの桁に2つ以上あるときにをとると0になってしまいますが、加算をすると繰り上がって1の位置がずれてしまいます。
ということは、区間のすべての桁について1の個数が1個または0個になるような区間を求めれば答えを求めることができることがわかります。
というのが解説にもありますが、区間を尺取りで実際に計算しながら求めれば答えを求めるのには十分です。
数える実装が上手くきれいに書けなくてサンプルがなかなか通らなかったです。 結局右側を順番に回して左側を詰めていく実装に落ち着きました。 あとほかの人の実装が頭よかったので参考にしました。