아름답지 않은 수열

$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 0 \pmod 4$이거나 $N \equiv 1 \pmod 4$인 경우를 제외하고는 항상 조건을 만족하는 수열을 구성할 수 있다.

구성은 다음과 같다.

$N \equiv 2 \pmod 4$인 경우,

$$A= (2,5,N-1,6,7,N-2,1, 8\oplus2,9\oplus2,\ldots,(N-2)\oplus2, 4,3)$$

$N \equiv 3 \pmod 4$인 경우,

$$A= (5,1,6,N-3,3,N-2,4, 8\oplus2,9\oplus2,\ldots,(N-2)\oplus2, 7,2)$$

먼저 이 수열이 순열임을 확인하자.

$N \equiv 2 \pmod 4$이면

$$\{i\oplus2 \mid 8 \le i \le N-2\} = \{8,9,\ldots,N-3,N\}$$

이고, 나머지 수

$$1,2,3,4,5,6,7,N-2,N-1$$

은 따로 한 번씩 등장한다.

$N \equiv 3 \pmod 4$이면

$$\{i\oplus2 \mid 8 \le i \le N-2\} = \{8,9,\ldots,N-4,N-1,N\}$$

이고, 나머지 수

$$1,2,3,4,5,6,7,N-3,N-2$$

은 따로 한 번씩 등장한다. 따라서 두 경우 모두 $A$는 $1,2,\ldots,N$의 순열이다.

이제 두 번째 조건을 만족함을 보이자. prefix XOR을

$$P_0=0,\qquad P_i=A_1\oplus A_2\oplus\cdots\oplus A_i$$

로 둔다. 구간 $[l,r]$의 XOR은

$$A_l\oplus A_{l+1}\oplus\cdots\oplus A_r = P_{l-1}\oplus P_r$$

이다. $a=l-1$, $b=r$라 두면 항상

$$0\le a<b\le N$$

이다.

구간 XOR이 오른쪽 끝점 $r$과 같다면

$$P_a\oplus P_b=b$$

이고, 이는

$$P_a=P_b\oplus b$$

와 동치이다.

구간 XOR이 왼쪽 끝점 $l$과 같다면

$$P_a\oplus P_b=a+1$$

이고, 이는

$$P_b=P_a\oplus(a+1)$$

와 동치이다.

따라서 위 두 등식이 $0\le a<b\le N$에서 성립하지 않음을 보이면 충분하다.

먼저 $N\equiv2\pmod4$인 경우를 보자. prefix XOR은 다음과 같다. 가운데 네 열은 $8\le i\le N-2$인 경우이다.

$$\begin{array}{c|cccccccc|cccc|cc} i &0&1&2&3&4&5&6&7 &i\equiv0&i\equiv1&i\equiv2&i\equiv3 &N-1&N\\ \hline P_i &0&2&7&(N-2)\oplus6&N-2&(N-2)\oplus7&7&6 &i\oplus4&7&i\oplus5&6 &N-2&(N-2)\oplus3 \end{array}$$

이 표에서, $0\le a,b\le N$에 대해

$$P_a=P_b\oplus b$$

가 성립하는 경우 중 $b\ge1$인 것은

$$(a,b)=(N-2,4)$$

뿐이다. 이때 $N\ge10$이므로 $a>b$이다.

또한

$$P_b=P_a\oplus(a+1)$$

가 성립하는 경우 중 $0\le a\le N-1$, $b\ge1$인 것은

$$(a,b)=(N-3,3),\ (N-1,1)$$

뿐이다. 두 경우 모두 $a>b$이다.

따라서 $N\equiv2\pmod4$인 경우에는 조건을 만족하지 않는 구간이 존재하지 않는다.

이제 $N\equiv3\pmod4$인 경우를 보자. prefix XOR은 다음과 같다. 가운데 네 열은 $8\le i\le N-2$인 경우이다.

$$\begin{array}{c|cccccccc|cccc|cc} i &0&1&2&3&4&5&6&7 &i\equiv0&i\equiv1&i\equiv2&i\equiv3 &N-1&N\\ \hline P_i &0&5&4&2&(N-3)\oplus2&(N-3)\oplus1&0&4 &i\oplus6&5&i\oplus7&4 &2&0 \end{array}$$

이 표에서

$$P_a=P_b\oplus b$$

가 성립하는 경우 중 $b\ge1$인 것은 다음뿐이다.

첫째, $b=1$이고 $P_a=4$인 경우이다. 이때 표에서 $P_a=4$가 되는 모든 인덱스는 $a>1=b$이다.

둘째,

$$(a,b)=(N-3,4)$$

인 경우이다. $N\ge10$이므로 이때도 $a>b$이다.

따라서 첫 번째 등식은 $a<b$에서 성립하지 않는다.

또한

$$P_b=P_a\oplus(a+1)$$

가 성립하려면

$$a=N-1,\qquad P_b=N-2$$

이어야 한다. 그런데 $P_{N-1}=2$, $P_N=0$이므로 $P_b=N-2$가 되려면 반드시 $b<N-1=a$이다. 따라서 두 번째 등식도 $a<b$에서 성립하지 않는다.

결국 $N\equiv3\pmod4$인 경우에도 조건을 만족하지 않는 구간이 존재하지 않는다.

따라서 위 구성은 모든 가능한 $N$에 대해 조건을 만족하는 수열이 된다. 시간 복잡도는 $O(N)$이다.

Solution written by GPT5.5