Pebble Game

각 더미의 게임 값을 $g(x)$라고 정의한다. 다음 식으로 계산할 수 있다.

• $x \bmod 6$이 $1$ 또는 $2$라면 $g(x)=0$이다.
• 그렇지 않으면 $t=\lfloor (x-3)/6 \rfloor$로 놓는다. $t$의 3진법 표현을 오른쪽에서부터 확인해, 처음으로 $0$이 나올 때까지 연속된 0이 아닌 자릿수의 개수를 $c$라 하면 $g($이다. 일 때에는 이다.

정답은 $g(A_1)\oplus g(A_2)\oplus\cdots\oplus g(A_N)$이 이면 , 아니면 이다.

이 게임에서는 현재 차례인 사람이 더미를 세 부분으로 나누고, 상대가 남길 부분을 선택한다. 한 더미에서 값 $h$로 반드시 바꿀 수 있다는 것은, 세 부분의 게임 값이 모두 $h$인 분할이 존재한다는 뜻이다. 따라서 다음 집합을 정의한다.

$$S(x)=\{h\mid a+b+c=x,\ a,b,c\ge 1,\ g(a)=g(b)=g(c)=h\}.$$

위에 정의한 $g$는 $g(x)=\operatorname{mex}S(x)$를 만족한다. 실제로 $g(x)=k$이면 모든 에 대해 세 부분의 게임 값이 모두 인 분할이 존재하지만, 모두 인 분할은 없다.

이를 확인하려면 $x=6t+r$ ($3\le r\le 6$)로 쓰면 된다. 세 부분의 게임 값이 $h\ge 1$로 같으려면, 각 부분을 ()로 나타냈을 때 가 또는 여야 한다. 3진법으로 의 마지막 개 자릿수가 모두 또는 이고 그 다음 자릿수가 인 경우, 같은 조건을 만족하는 세 의 합으로는 과 를 만들 수 없다. 반면 더 작은 값 에 해당하는 세 는 자릿수별로 구성할 수 있다. 인 경우는 세 부분을 각각 또는 꼴로 만들면 된다. 인 경우에는 이 세 부분의 합으로 를 만들 수 없다.

마지막으로 모든 더미의 게임 값을 XOR한 결과가 $X$라고 하자. $X\ne0$이면 $X$의 최고로 높은 1비트를 가진 더미를 고르고, 그 더미의 값을 다른 모든 더미의 XOR로 강제하는 분할을 할 수 있다. 그러면 상대가 어느 부분을 남기더라도 다음 XOR는 $0$이다. $X=0$이면 어느 더미를 어떻게 나누어도 세 부분이 모두 기존 게임 값과 같을 수 없으므로, 상대는 XOR가 이 아닌 부분을 남길 수 있다. 따라서 위 판정이 성립한다.

각 수에서 3진법 자릿수를 많아야 $O(\log_3 A_i)$개 확인하므로 전체 시간 복잡도는 $O(\sum N\log_3 \max A_i)$이고, 추가 공간 복잡도는 이다.