ARC 045 C - エックスオア多橋君

• 問題
• AC

まずは列に関する同等の問題を解く。つまり、区間の総XORが$X$になるような区間の総数を求める問題を考える。頂点を0-basedで与えて$0, 1, ..., N-1$とし、区間$[0, k)$の総XORを$S[k]$で表すことにする。区間$[l, r)$の総XORは$S[r] \oplus S[l]$と書けて、これが$X$に等しいという条件を整理すると

$$S[l] = S[r] \oplus X$$

となる。つまり、$r = 0$から順に、$S[r] \oplus X$に等しいような$S[i], i \in [0, r)$が何個あるか数えればよくて、これはハッシュテーブルなどに$S[i]$の出現回数を記録していけば${O}(N)$でできる。

木に関してもオイラーツアーを考えれば同じようにできるが、列の場合の方針をそのまま適用すると、同じ頂点を重複して数えることになってしまう。対処は簡単で、pre-orderに対応するものだけ数えるとか決めておけばよい。