ABC150 F. Xor Shift

問題

非負整数からなる長さNの数列a_iとb_iが与えられる。
今、0 <= k < Nを満たす整数kと、0以上の整数xを決めて、新しく長さNの数列a'_iを
「a'_i = a_{(i+k) mod N} xor x」
のように定める。

a'がbと等しくなるような(k, x)のペアを全て求めよ。

制約

• 1 <= N <= 2*10^5
• 0 <= a_i, b_i < 2^30

解法

まず、条件をできるだけ数式で考える。
a'はaをkだけローテートしたものとxのxorしたものになっている。
ここで、前者の「aをkだけローテートした数列をs」とする。
条件は「s_i xor x = b_i」なので、「s_i xor b_i = x」であり「s_iとb_iのxorが一定(=x)」ということになる。
s_jとb_jについても同じなので、「s_i xor b_i = s_j xor b_j」が0 <= i,j < Nで成り立つ。
式を変形すると、「s_i xor s_j = b_i xor b_j」で、j=i+1でも同じなので、結局、「xは考えなくてよく、数列sの隣り合う要素のxorからなる数列s'と、数列bの隣り合う要素のxorからなる数列b'が一致すればよい」ということになる。

数列sは数列aをローテートしただけなので、結局、数列aの隣り合う要素のxorからなる数列を求めておいて、それを2つ並べたところから数列b'と一致する部分を求める問題になる。

これは文字列検索の文脈のZAlgorithmやKMPで求められる。
ZAlgorithmでO(N)で求められる。