各ボールから見た \(L,R\) の列を計算します。 数列全体の xor が \(0\) であることから、これは両端に設置した \(Z\) も含めた先頭からの累積 xor 列において、その項の直前と直後の項に対応します。 次に、\(2\) つのボールが同じ座標に来た時の様子を見ると、 先ほど求めた累積 xor 列の中で、同じ座標になった 2 つのボールの間にあった項が無くなることに対応しています。また、ボールの運動の規則より、ボールは累積 xor 列の前後の項のうち大きい項に向かって運動していることが分かります。

したがって、ボールの運動は、累積 xor 列で左右どちらよりも大きい項（正確には、左右どちらよりも小さくなく、どちらかよりは大きい項）があれば、その項を消去して数列を繋げることと同一視できます。 ボールの運動が静止することは、その時点で数列に存在している全ての項が等しい値になることと等価です。 そして、これを実現するための必要十分条件は、両端に存在する \(Z\) よりも小さい項が存在しないことです。

以上から、この問題は 「\(Z=0\) として計算した累積 xor の数列 \(p_i\) があります。 \(2^N-1\) 以下の整数 \(Z\) であって、\(Z\) xor \(p_i\) の全てが \(Z\) より小さくならないものの数を求めてください。」 という問題と等価であると言えます。 \(Z>(Z\) xor \(p_i)\) となるのは、\(p_i\) の最上位 bit を \(Z\) が持っている場合です。 したがって、全ての \(p_i\) について最上位 bit を確認したとき、一度も登場していない bit が \(k\) 個であるとすると、答えは \(2^k\) です。