1⊕2⊕⋯⊕N의 값은 Nmod4에 따라 각각
N, 1, N+1, 0
이다. 구간 (1,N)도 조건을 만족해야 하므로, N≡0(mod4)이면 전체 XOR이 N이 되어 불가능하고, N≡1(mod4)이면 전체 XOR이 1이 되어 불가능하다.
N<10인 경우에는 가능한 모든 수열을 확인하면 N=2에서만 수열 [2,1]만 조건을 만족하는 수열임을 알 수 있다. N≥10인 경우는 N≡0(mod4)이거나 N≡1(mod4)인 경우를 제외하고는 항상 조건을 만족하는 수열을 구성할 수 있다.
구성은 다음과 같다.
N≡2(mod4)인 경우,
A=(2,5,N−1,6,7,N−2,1,8⊕2,9⊕2,…,(N−2)⊕2,4,3)
N≡3(mod4)인 경우,
A=(5,1,6,N−3,3,N−2,4,8⊕2,9⊕2,…,(N−2)⊕2,7,2)
먼저 이 수열이 순열임을 확인하자.
N≡2(mod4)이면
{i⊕2∣8≤i≤N−2}={8,9,…,N−3,N}
이고, 나머지 수
1,2,3,4,5,6,7,N−2,N−1
은 따로 한 번씩 등장한다.
N≡3(mod4)이면
{i⊕2∣8≤i≤N−2}={8,9,…,N−4,N−1,N}
이고, 나머지 수
1,2,3,4,5,6,7,N−3,N−2
은 따로 한 번씩 등장한다. 따라서 두 경우 모두 A는 1,2,…,N의 순열이다.
이제 두 번째 조건을 만족함을 보이자. prefix XOR을
P0=0,Pi=A1⊕A2⊕⋯⊕Ai
로 둔다. 구간 [l,r]의 XOR은
Al⊕Al+1⊕⋯⊕Ar=Pl−1⊕Pr
이다. a=l−1, b=r라 두면 항상
0≤a<b≤N
이다.
구간 XOR이 오른쪽 끝점 r과 같다면
Pa⊕Pb=b
이고, 이는
Pa=Pb⊕b
와 동치이다.
구간 XOR이 왼쪽 끝점 l과 같다면
Pa⊕Pb=a+1
이고, 이는
Pb=Pa⊕(a+1)
와 동치이다.
따라서 위 두 등식이 0≤a<b≤N에서 성립하지 않음을 보이면 충분하다.
먼저 N≡2(mod4)인 경우를 보자. prefix XOR은 다음과 같다. 가운데 네 열은 8≤i≤N−2인 경우이다.
iPi0012273(N−2)⊕64N−25(N−2)⊕76776i≡0i⊕4i≡17i≡2i⊕5i≡36N−1N−2N(N−2)⊕3
이 표에서, 0≤a,b≤N에 대해
Pa=Pb⊕b
가 성립하는 경우 중 b≥1인 것은
(a,b)=(N−2,4)
뿐이다. 이때 N≥10이므로 a>b이다.
또한
Pb=Pa⊕(a+1)
가 성립하는 경우 중 0≤a≤N−1, b≥1인 것은
(a,b)=(N−3,3), (N−1,1)
뿐이다. 두 경우 모두 a>b이다.
따라서 N≡2(mod4)인 경우에는 조건을 만족하지 않는 구간이 존재하지 않는다.
이제 N≡3(mod4)인 경우를 보자. prefix XOR은 다음과 같다. 가운데 네 열은 8≤i≤N−2인 경우이다.
iPi001524324(N−3)⊕25(N−3)⊕16074i≡0i⊕6i≡15i≡2i⊕7i≡34N−12N0
이 표에서
Pa=Pb⊕b
가 성립하는 경우 중 b≥1인 것은 다음뿐이다.
첫째, b=1이고 Pa=4인 경우이다. 이때 표에서 Pa=4가 되는 모든 인덱스는 a>1=b이다.
둘째,
(a,b)=(N−3,4)
인 경우이다. N≥10이므로 이때도 a>b이다.
따라서 첫 번째 등식은 a<b에서 성립하지 않는다.
또한
Pb=Pa⊕(a+1)
가 성립하려면
a=N−1,Pb=N−2
이어야 한다. 그런데 PN−1=2, PN=0이므로 Pb=N−2가 되려면 반드시 b<N−1=a이다. 따라서 두 번째 등식도 a<b에서 성립하지 않는다.
결국 N≡3(mod4)인 경우에도 조건을 만족하지 않는 구간이 존재하지 않는다.
따라서 위 구성은 모든 가능한 N에 대해 조건을 만족하는 수열이 된다. 시간 복잡도는 O(N)이다.
Solution written by GPT5.5
