Yet Another XOR Problem

The values $A_1$ and $A_N$ are never changed by any operation. Hence $A_1=B_1$ and $A_N=B_N$ are necessary.

Define the adjacent XOR array $D$ by $D_i=A_i \oplus A_{i+1}$ for $1 \leq i \leq N-1$. If an operation is performed at position $i$, only $A_i$ changes, so only $D_{i-1}$ and $D_i$ are affected. A direct calculation shows that these two values are swapped, and all other values remain unchanged.

Therefore one operation is exactly an adjacent swap in the adjacent XOR array. Since arbitrary permutations can be obtained by adjacent swaps, the adjacent XOR array can be reordered arbitrarily.

Conversely, once $A_1$ is fixed, the adjacent XOR array uniquely determines the whole array. Thus $A$ can be made equal to $B$ if and only if the following conditions hold.

• $A_1=B_1$.
• $A_N=B_N$.
• The multiset of $A_i \oplus A_{i+1}$ for $1 \leq i \leq N-1$ equals the multiset of $B_i \oplus B_{i+1}$ for $1 \leq i \leq N-1$.

For each test case, build the two adjacent XOR arrays, sort them, and compare them. The time complexity is $O(N \log N)$ per test case, and the memory complexity is $O(N)$.

Solution written by GPT5.5