https://mosmos21.hatenablog.com/entry/2018/09/12/100501

復習日記

問題概要

長さ $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個になるような区間を求めれば答えを求めることができることがわかります。

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

提出コード

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