\(k\) を固定すると、条件を満たす \(x\) は、存在すれば一意に定まり、 \(x = b_0 \,\text{xor}\,a_k\) です。

条件を満たす \(x\) が存在する時、\(i = 0, 1, \ldots, N\) について、\(a_{i + k \mod N} \,\text{xor}\, x = b_i\) が成り立ちます。
ここで、xor はビットごとに独立に計算できることを踏まえると、\(a, b\) は \(2^{30}\) 以下の非負整数の列であるため、\(a, b\) が 01 のみからなる場合の問題を 30 個解くことで計算することができます。

\(a, b\) が 0, 1 のみからなる場合、条件を満たす \(x\) としてありうるのは 0 または 1 のみです。

よって、\(a_{i + k \mod N} = b_i \; (i = 0, 1, \ldots, N)\) か \(1 \,\text{xor} \,a_{i + k \mod N} = b_i \; (i = 0, 1, \ldots, N)\) が成り立つかどうかを全ての k について計算すればよく、これは公式解説などの方法で \(O(N)\) で計算できます。

以上の方法で、\(a, b\) が \(d\) ビットの整数で構成されているとした時、この問題を \(O(Nd)\) で解くことができました。