아름답지 않은 수열

$1 \oplus 2 \oplus \cdots \oplus N$의 값은 $N \bmod 4$에 따라 각각 $N,1,N+1,0$이다. 전체 구간 $(1,N)$도 조건을 만족해야 하므로, $N \equiv 0 \pmod 4$이면 전체 XOR이 $N$이 되어 불가능하고, $N \equiv 1 \pmod 4$이면 전체 XOR이 $1$이 되어 불가능하다.

$N<10$인 경우는 모든 순열을 확인하면 $N=2$의 수열 $[2,1]$만 가능하다.

이제 $N \geq 10$이고 $N \equiv 2,3 \pmod 4$인 경우를 구성한다. 아래의 고정 수열들은 직접 조건을 만족한다.

$$\begin{aligned} B_2={}&[2,1],\\ B_{10}={}&[2,1,4,5,6,9,3,10,8,7],\\ B_{14}={}&[2,1,4,5,6,14,3,13,11,9,8,10,12,7],\\ B_{18}={}&[2,1,4,5,6,14,3,13,11,9,8,10,12,7,16,17,18,15],\\ B_{22}={}&[2,1,4,5,6,14,3,13,11,9,8,10,12,7,16,17,19,21,22,18,20,15],\\ B_{26}={}&[2,1,4,5,6,14,3,13,11,9,8,10,12,7,16,17,19,25,26,22,24,20,18,15,21,23],\\ B_{30}={}&[2,1,4,5,6,14,3,13,11,9,8,10,12,7,16,19,22,17,21,26,20,30,28,25,23,18,24,29,15,27],\\ B_{34}={}&B_{30}+[32,33,34,31],\\ B_{38}={}&B_{30}+[33,34,32,35,37,38,36,31]. \end{aligned}$$

$N \equiv 2 \pmod 4$이고 $N>38$이면 $B_{38}$에서 마지막 원소 $31$을 잠시 제외한다. 현재 길이가 $M$일 때마다

$$[M+1,\ M+3,\ M+4,\ M+2]$$

를 뒤에 붙이고 $M$을 $M+4$로 바꾼다. 원하는 길이에 도달하면 마지막에 $31$을 붙인다.

$N \equiv 3 \pmod 4$인 경우에는 다음 세 수열을 시작점으로 사용한다.

$$\begin{aligned} C_{11}={}&[3,4,1,6,7,9,2,11,10,5,8],\\ C_{15}={}&[3,4,1,6,7,9,2,15,11,8,14,13,5,10,12],\\ C_{19}={}&[3,4,1,6,7,9,2,15,11,8,14,13,5,10,17,18,19,12,16]. \end{aligned}$$

$N>19$이면 현재 길이가 $M$이고 수열의 마지막 두 원소가 $12,M-3$일 때, 이 두 원소를 지우고

$$[M-3,\ M+2,\ M+3,\ M+4,\ 12,\ M+1]$$

을 붙인다. 그러면 새 길이는 $M+4$이고 마지막 두 원소는 다시 $12,(M+4)-3$이므로 반복할 수 있다.

각 반복 규칙은 기존 구간 중 영향을 받지 않는 구간을 그대로 보존한다. 새로 생기거나 끝점이 바뀌는 구간의 XOR 값은 위에 추가한 네 개의 새 수와 보존된 꼬리 원소만으로 정해지며, $M \equiv 2$ 또는 $M \equiv 3 \pmod 4$를 대입해 확인하면 어떤 경우에도 새 왼쪽 끝점이나 오른쪽 끝점과 같지 않다. 따라서 시작 수열의 직접 확인과 반복 규칙의 귀납 적용으로 모든 가능한 $N$에 대해 수열을 구성할 수 있다.

구성은 각 원소를 한 번씩 출력하므로 시간 복잡도는 $O(N)$이다.

Solution written by GPT5.5