Adjacent XOR

The operation at index $i$ is:

$$a_i := a_i \oplus a_{i+1}$$

and each index $i<n$ can be used at most once.

The annoying-looking part is that operations can be done in any order, so $a_{i+1}$ might already have changed when we use it. But the structure is much simpler than it first looks.

What can change what?

Operation $i$ changes only $a_i$.

So:

• $a_n$ never changes.
• $a_i$ can only be changed by operation $i$.
• $a_{i+1}$ can only be changed by operation $i+1$.

That last point is the entire problem.

When we perform operation $i$, the current value of $a_{i+1}$ is one of two things:

1. operation $i+1$ has not happened yet, so the value is the original $a_{i+1}$;
2. operation $i+1$ has already happened, so the value is final, namely $b_{i+1}$.

There is no way for $a_{i+1}$ to be changed twice, and no other operation touches it. So those are the only possibilities. Not “some XOR of a whole suffix”, not magic, just two values.

Local condition

For position $i<n$, there are three ways to end with $b_i$:

• do not use operation $i$, so $b_i=a_i$;
• use operation $i$ before operation $i+1$, so

$$b_i = a_i \oplus a_{i+1};$$

• use operation $i$ after operation $i+1$, so

$$b_i = a_i \oplus b_{i+1}.$$

So position $i$ is valid exactly when:

$$b_i \in \{a_i,\ a_i\oplus a_{i+1},\ a_i\oplus b_{i+1}\}.$$

For the last position, we only need:

$$a_n=b_n.$$

Why local checks are enough

The only remaining worry is: what if every position looks valid alone, but the required operation order contradicts itself globally?

It cannot.

If operation $i$ needs the original $a_{i+1}$, then operation $i$ should happen before operation $i+1$.

If operation $i$ needs the final $b_{i+1}$, then operation $i+1$ should happen before operation $i$.

These constraints are only between neighboring operations, forming a directed version of a path. A directed cycle would require an undirected cycle, and a path has none. So some valid ordering always exists.

That means the simple check is not just necessary, it is sufficient too.

Algorithm

For each test case:

1. If $a_n \ne b_n$, answer NO.
2. For every $i$ from $1$ to $n-1$, check whether at least one of these is true:
   • $b_i=a_i$;
   • $b_i=a_i\oplus a_{i+1}$;
   • $b_i=a_i\oplus b_{i+1}$.
3. If all checks pass, answer YES; otherwise answer NO.

Complexity

Each index is checked once.

Time complexity: $O(n)$ per test case.

Memory complexity: $O(n)$ for the arrays.