L 모양은 한 열의 두 칸과 인접한 열의 한 칸을 차지한다. 따라서 한 번 움직이면 반드시 빈 열이 생기고, 그 양쪽은 서로 영향을 주지 않는 독립적인 게임이 된다.
빈 열로 나눈 각 구간에서는 양 끝 열에 한 칸만 남을 수 있고, 내부 열에는 항상 두 칸이 남아 있다. 이 성질은 모든 이동 후에도 유지된다.
구간에 남은 칸 수를 라고 하자. 어떤 이동을 하더라도 두 구간의 칸 수는 와 가 된다. 반대로 인 모든 분할을 만들 수 있다. 칸을 왼쪽 열부터 나열하면 연속한 세 칸은 항상 한 열의 두 칸과 이웃 열의 한 칸이므로, 앞의 칸 다음에 오는 세 칸을 가져가면 된다. 다른 방향의 L을 골라도 가능한 두 구간의 크기는 이 범위를 벗어나지 않는다.
따라서 구간의 그런디 수는 구체적인 모양이 아니라 칸 수만으로 정해진다. 이를 라 하면
이고, 에서는
이다. 는 집합에 없는 가장 작은 음이 아닌 정수이고, 는 비트 XOR이다.
처음에는 개의 칸이 하나의 구간을 이룬다. 이면 YES, 아니면 NO를 출력한다.
입력에서 가장 큰 을 이라 하면 부터 까지 시간과 공간에 전처리한다. 각 테스트 케이스는 시간이므로 전체 시간복잡도는 이다. 입력 저장까지 포함한 공간복잡도는 이다.
서브태스크 1은 이다. 개 칸의 남은 상태를 비트마스크로 표현하고, 가능한 모든 L 모양을 시도하는 메모이제이션 탐색으로 해결한다. 서로 다른 의 결과를 재사용하면 에 대해 시간과 이하의 공간이 충분하다. 서브태스크 2는 위의 그런디 수 점화식으로 해결한다.
Solution written by GPT
