Yet Another XOR Problem

$A_1$과 $A_N$은 어떤 연산으로도 바뀌지 않는다. 따라서 $A_1=B_1$과 $A_N=B_N$이 필요하다.

인접 XOR 배열 $D$를 $D_i=A_i \oplus A_{i+1}$ ($1 \leq i \leq N-1$)로 정의하자. 위치 $i$에 연산을 수행하면 $A_i$만 바뀌고, $D_{i-1}$과 $D_i$만 영향을 받는다. 계산하면 두 값이 서로 바뀌고 나머지 원소는 변하지 않는다.

즉 한 번의 연산은 인접 XOR 배열에서 서로 이웃한 두 원소를 swap하는 것과 같다. 이웃한 두 원소의 swap을 원하는 만큼 할 수 있으므로 인접 XOR 배열의 원소들은 임의의 순서로 재배열될 수 있다.

반대로 $A_1$이 정해져 있으면 인접 XOR 배열은 전체 배열을 유일하게 결정한다. 따라서 $A$를 $B$로 만들 수 있는 필요충분조건은 다음과 같다.

• $A_1=B_1$.
• $A_N=B_N$.
• $A_i \oplus A_{i+1}$ ($1 \leq i \leq N-1$)들의 멀티셋과 $B_i \oplus B_{i+1}$ ($1 \leq i \leq N-1$)들의 멀티셋이 같다.

각 테스트 케이스마다 두 인접 XOR 배열을 만든 뒤 정렬하여 비교하면 된다. 전체 시간 복잡도는 $O(N \log N)$이고, 전체 메모리 복잡도는 $O(N)$이다.

Solution written by GPT5.5