제3회 초콜릿컵

## 풀이

* 주어진 수식에 대해, 시작 부분의 느낌표의 개수 $a$, 중간의 정수 $x$, 끝 부분의 느낌표의 개수 $b$를 구합니다.
* 팩토리얼을 먼저 계산합니다. $b \ne 0$이면 $x$를 $1$로 바꿉니다. $b$번 루프를 돌아도 상관 없습니다.
* 그다음 논리 반전을 계산합니다. $a$가 짝수이면 $x$를 그대로 두고, 홀수이면 $0$이나 $1$을 $1$이나 $0$으로 바꿉니다. 이것도 $a$번 루프를 돌아도 상관 없습니다.
* 모든 과정이 끝났을 때 $x$의 값을 출력하면 됩니다.

제3회 초콜릿컵 - A - Editorial

## 풀이

* $N \ge 4$라면, 여러 가지 방법으로 $11$의 배수인 $N$자리 팰린드롬을 만들 수 있습니다.
  * $11 \underbrace{000\cdots000}_{N-4} 11 = 11 \times (10^{N-2} + 1)$
  * $1 \underbrace{222\cdots222}_{N-2} 1 = 11 \times \underbrace{111\cdots111}_{N-1}$
* $N \le 3$일 때 가능한 답은 다음과 같습니다.
  * $N = 1$: $0$
  * $N = 2$: $11$, $22$, $33$, $44$, $55$, $66$, $77$, $88$, $99$
  * $N = 3$: $121$, $242$, $363$, $484$, $616$, $737$, $858$, $979$

## 별해

* $N$이 짝수인 경우, $1 \underbrace{000 \cdots 000}_{N-2} 1$도 $11$의 배수입니다.
* $N$자리의 팰린드롬을 랜덤으로 생성하여 $11$의 배수가 나올 때까지 반복하는 풀이도 가능합니다.
* 랜덤 풀이가 가능한 이유는, $N$이 짝수일 경우 **모든 팰린드롬이 $11$의 배수**이고, 홀수인 경우에는 임의의 팰린드롬이 $11$의 배수일 확률이 $\frac{1}{11}$에 수렴하므로 평균 $11$회 시도에 올바른 답을 얻을 수 있기 때문입니다.

제3회 초콜릿컵 - B - Editorial

## 풀이

* ㄱ나이트는 오른쪽 아래로만 이동할 수 있으므로, 맨 왼쪽 위부터 순서대로 돌면서 놓을 수 없는 곳을 제외하고 그리디하게 놓으면 최적이 됩니다.
* 문제 범위가 $TXY \le 2\;500\;000$이므로, 위의 풀이를 그대로 시뮬레이션하여 풀 수 있습니다.

## 풀이의 증명

* 각 칸을 정점으로 하고 "두 칸 모두에 ㄱ나이트를 올릴 수 없다"라는 관계를 간선으로 하는 그래프를 생각합니다.
* 그러면, 정점 $(x_0, y_0)$을 포함하는 연결 요소는

  $$ \cdots, (x_0 - 2x, y_0 - 2y), (x_0 - x, y_0 - y), (x_0, y_0), (x_0 + x, y_0 + y), (x_0 + 2x, y_0 + 2y), \cdots $$

  가 일렬로 연결된 선 그래프가 됩니다.
* $n$개의 정점을 갖는 선 그래프에서 최대 독립 집합의 크기는 $\lceil\frac{n}{2}\rceil$이며, 이는 한쪽 끝 정점에서부터 그리디하게 정점을 선택하여 얻는 답과 같습니다.

제3회 초콜릿컵 - C - Editorial

## 풀이

* 맨 윗줄부터 아래로, 왼쪽에서 오른쪽 순서로 각 칸을 다음과 같이 검사합니다.
  * 이미 다른 삼각형의 일부라면 넘어갑니다.
  * `R`을 만나면, 현재 칸을 맨 위 칸으로 하는 `R` 삼각형을 놓습니다. 이것이 불가능하다면 답은 `0`입니다.
  * `B`를 만나면, 현재 칸을 맨 윗줄 왼쪽 칸으로 하는 `B` 삼각형을 놓습니다. 이것이 불가능하다면 답은 `0`입니다.
* 모든 칸이 채워졌다면 답은 `1`입니다.
* 이 알고리즘은 칸의 개수에 대한 선형, 즉 $\mathcal{O} (N^2)$에 동작합니다.
* 이 알고리즘이 올바른 답을 내놓는 이유는, 현재 칸의 위쪽과 왼쪽에 있는 칸을 사용하지 않고 현재 칸에 `R`이나 `B` 삼각형을 놓는 방법이 하나뿐이기 때문입니다.

제3회 초콜릿컵 - D - Editorial

## 노트

* 이 문제는 대회 종료 후 지문이 변경되었습니다. 아래 풀이는 변경된 지문을 기준으로 합니다.

## 풀이

* 2단계의 조건을 다른 말로 쓰면, 하나의 단위 조각을 제거한 후 남아있는 초콜릿이 하나의 트리를 이루어야 한다는 뜻이 됩니다.
* 각각의 단위 조각을 제거하였을 때 남은 부분이 연결되었는지, 그것이 트리인지는 각각 $\mathcal{O} (V+E) = \mathcal{O} (N^2)$에 계산할 수 있으므로, 이를 모든 조각에 대해 반복하는 것으로 문제를 해결할 수 있습니다.
* 총 시간 복잡도는 $\mathcal{O} (N^4)$입니다.

제3회 초콜릿컵 - E - Editorial

## 풀이

* 어떤 정점 $(x_0, y_0)$에서 왼쪽으로 갔다가 다시 같은 $x$좌표로 돌아오는 경로를 생각해 봅시다. 이러한 경로를 $C$형 경로라고 합시다.
* 이 경로가 포함하는 정점의 최소 $x$좌표를 $x_\text{min}$이라고 합시다.
* 그러면, $x_\text{min} < x < x_0$인 $x$에 대해 $(x, 1)$과 $(x, 2)$를 모두 거쳐야 함을 관찰할 수 있습니다.
* 정점의 점수의 합은 두 정점의 방문 순서와는 관계가 없으므로, $(x_\text{min}, 1)$과 $(x_\text{min}, 2)$ 중 어느 곳을 거치는가에 따라 3가지 가능성만 존재합니다.
* 가능한 모든 $x_\text{min}$에 대한 점수의 합들을 효율적으로 구하려면, $x_0$에서 왼쪽 방향으로 $(x, 1)$과 $(x, 2)$의 점수의 합에 대한 누적합을 이용할 수 있습니다.

### $a = c$인 경우

* 코코의 가게에서 왼쪽으로 출발하면 가게의 오른쪽을 방문할 수 없고 (한별이의 가게에서 경로가 끝나기 때문), 반대도 마찬가지입니다.
* 따라서 이 경우는 왼쪽과 오른쪽의 두 경우에 대해 $C$형 경로의 점수의 최댓값을 구하고, 그 둘의 최댓값을 출력하면 됩니다.

### $a \ne c$인 경우

* 일반성을 잃지 않고 $a < c$라고 합시다. 반대라면 시작 좌표와 끝 좌표를 서로 바꿔서 계산하면 같은 답을 얻을 수 있습니다.
* 그러면 $(a, b)$에서 출발하는 방법은 오른쪽, 세로 방향, 왼쪽의 3가지가 있습니다.
  * 왼쪽으로 출발하면 $C$형 경로를 거쳐서 $(a, 3-b)$를 지나게 됩니다.
  * 세로 방향으로 출발하면 다음에는 오른쪽으로 가야 하므로 $C$형 경로의 특수한 경우가 됩니다.
  * 오른쪽으로 출발하면 $x \le a$인 정점은 출발점 하나만 거치거나, 출발점과 $(a, 3-b)$를 거치는 방법이 있습니다. 후자는 세로 방향으로 출발한 것과 중복되므로 무시해도 됩니다.
* $(c, d)$에 도착하는 방법도 마찬가지로 분류하여 $x \ge c$인 정점들을 처리할 수 있습니다.
* 이제 $a < x < c$의 범위에 있는 정점들을 생각해 봅시다.
* $(a, ?)$에서 $(c, ?)$로 가려면 모든 $a < x < c$에 대해 $(x, ?)$를 적어도 하나 거쳐야 합니다.
  * $(x, 1)$과 $(x, 2)$를 모두 거치는 것도 물론 가능합니다.
* 이동 도중에 역방향으로 꺾을 수 있으나, 오른쪽 또는 세로로만 이동하는 경로로도 같은 가게의 집합을 방문할 수 있으므로 이 경우는 무시해도 됩니다.
* 따라서, 각각의 $x$에 대해 하나 또는 두 곳을 방문하는 총 3가지 경우 중에서 최댓값을 선택하면 됩니다.

제3회 초콜릿컵 - F - Editorial

## 풀이

### 관찰

* **Claim:** 게임을 시작할 때의 배치에서 $H$가 홀수 개이면 승리하고, 짝수 개이면 패배합니다.
* 수학적 귀납법으로 증명합니다.
* 먼저 초콜릿의 개수 $N$이 $1$인 경우, $H$에서는 유일한 $H$를 제거하면 승리하고, $T$에서는 아무것도 제거할 수 없으므로 패배합니다.
* 이제 $1 \le N \le M$인 경우에 대해 증명되었다고 가정하고 $N = M + 1$인 경우를 증명합니다.
* $H$가 홀수 개라면, $H$ 중에서 맨 왼쪽에 있는 것을 제거합니다.
  * 이것이 전체 초콜릿 중 맨 왼쪽이라면, $HH \cdots \rightarrow T\cdots$, $HT \cdots \rightarrow H\cdots$가 되므로 홀수 개의 $H$를 갖는 길이 $M$의 상태가 됩니다. 따라서 귀납적 가정에 의해 승리합니다.
  * 아닌 경우에는 초콜릿이 $2$개의 구간으로 나눠집니다. 왼쪽 구간에는 $H$가 $1$개, 오른쪽 구간에는 위와 같은 이유로 $H$가 홀수 개 존재하게 됩니다. 양쪽 구간 모두 길이가 $M$ 이하이므로, 귀납적 가정에 의해 승리합니다.
* $H$가 짝수 개라면, $H$ 중에서 어떤 것을 제거하더라도 한쪽 또는 유일한 구간에 $H$가 짝수 개 남아있음을 관찰할 수 있습니다. 이 구간은 길이가 $M$ 이하이므로 귀납적 가정에 의해 패배합니다.

### 계산

* 주어진 문자열에 `?`가 없을 경우에는 앞의 결과에 따라 `H`가 홀수 개면 $1$, 짝수 개면 $0$이 답이 됩니다.
* `?`가 있을 경우, 그 개수를 $k$라고 합시다.
* 각각의 `?`를 `H` 또는 `T`로 치환하는 경우의 수는 $2^k$개이며, 그 중에서 `H`가 홀수 개인 경우와 짝수 개인 경우는 모두 $2^{k-1}$입니다. 따라서 $2^{k-1} \operatorname{mod} P$를 계산하여 출력하면 됩니다.
* 별해 1: $n! \operatorname{mod} P$를 메모이제이션한 후 곱셈 역원을 이용해 이항 계수를 모두 구하고 그 합을 출력해도 됩니다.
* 별해 2: $i$번째 문자까지 `H`가 짝수 개인 경우의 수와 홀수 개인 경우의 수를 DP로 계산해도 됩니다.

제3회 초콜릿컵 - G - Editorial

## 풀이

* 한 변에 $N$개의 정육각형이 있는 삼각형을 $T_N$이라고 합시다.
* 먼저 $T_2$, $T_9$, $T_{11}$, $T_{12}$를 덮는 방법을 찾아봅시다.
  * $T_2$와 $T_9$를 덮는 방법은 입출력 예시에 있습니다.
  * $T_{11}$을 덮으려면, 위쪽 9줄을 $T_9$처럼 덮고, 마지막 2줄을 `R`과 `B`를 번갈아 써서 덮으면 됩니다.
  * $T_{12}$ 또한 $T_9$ 기반으로 비슷하게 덮을 수 있습니다.
* 이제 $T_{12k}$를 덮으려면, 정방향의 $T_{12}$를 $\frac{k(k+1)}{2}$개 배치하고 나면 남은 공간은 역방향의 $T_{11}$이 됨을 알 수 있습니다.
  * $T_{11}$을 역방향으로 만들 때 `R`과 `B`도 반전해야 함에 유의해야 합니다.
* 이제 $T_{12k+2}$, $T_{12k+9}$, $T_{12k+11}$을 채우면 문제가 해결됩니다.
  * $T_{12k+2}$와 $T_{12k+9}$의 경우, $T_{12k+12}$를 채워 놓고 마지막에 필요없는 줄을 버리면 해결됩니다.
  * $T_{12k+2}$의 경우, 정방향의 $T_{12}$의 첫 2줄은 $T_2$이고, 역방향의 $T_{11}$의 첫 2줄은 위쪽 $T_9$를 제외한 부분이므로 올바른 타일링입니다.
  * $T_{12k+9}$의 경우, 정방향의 $T_{12}$의 첫 9줄은 $T_9$이고, 역방향의 $T_{11}$의 첫 9줄은 위쪽 $T_2$를 제외한 부분이므로 올바른 타일링입니다.
  * $T_{12k+11}$은 마지막 12줄에 올 $T_{12}$들을 $T_{11}$로 대체하면 됩니다.

제3회 초콜릿컵 - H - Editorial

## 풀이

* ㄱ나이트의 이동 규칙을 간선으로 하는 그래프에서 최대 독립 집합의 크기를 구하는 문제입니다.
* 하나의 연결 요소만 생각해 보면, 이 그래프는 격자 그래프와 같은 형태를 이루므로 이분 그래프가 됩니다.
* 이분 그래프에서 최대 독립 집합은 최소 정점 커버의 여집합이고, 최소 정점 커버의 크기는 쾨닉의 정리에 의해 최대 이분 매칭의 크기와 같습니다.
* 따라서, 각 연결 요소의 최대 이분 매칭의 크기를 구해서 모두 더한 값을 $XY$에서 빼면 그것이 정답이 됩니다.

### 부분 그래프의 분류

* 각 연결 요소의 형태를 잘 보면 합동인 그래프가 여러 개 만들어짐을 알 수 있습니다.
* 구체적으로, $XY$개의 칸을 이동 규칙에 의해 서로 이동 가능한 칸들의 집합으로 나누면 $2xy$개의 집합으로 나눌 수 있습니다. 이때 "ㄱ나이트는 초콜릿을 벗어날 수 없다"는 규칙은 무시합니다.
* $x$좌표가 $1$ 이상 $2x$ 이하, $y$좌표가 $1$ 이상 $y$ 이하인 $2xy$개의 칸은 모두 서로 다른 집합에 속하게 됩니다. 이러한 칸을 그 집합의 **대표 칸**이라고 합시다.
* 각 집합의 대표 칸의 좌표를 $(x_0, y_0)$라고 했을 때, $x_0$를 다음과 같이 4개의 구간으로, $y_0$를 2개의 구간으로 나누면, 대표 칸이 같은 구간에 속하는 두 집합의 그래프는 서로 합동입니다. ($r_x = X \operatorname{mod} x, r_y = Y \operatorname{mod} y$)
  * $ 1 \le x_0 \le r_x $, $r_x < x_0 \le x$, $x < x_0 \le x + r_x$, $x + r_x < x_0 \le 2x$
  * $1 \le y_0 \le r_y$, $r_y < y_0 \le y$

### 이분 매칭의 크기

* 이제 하나의 집합에 대해 최대 이분 매칭을 찾아야 합니다.
* 그 집합을 이분 그래프의 두 정점 집합으로 나누면, 각 집합이 포함하는 정점의 좌표는 $x$ 방향으로 $2x$ 간격, $y$ 방향으로 $2y$ 간격의 격자를 이룹니다.
* 이 집합은 그 집합이 포함하는 $x$좌표의 개수 $a$와 $y$좌표의 개수 $b$로 나타낼 수 있으며, 전체 그래프는 두 개의 정수 쌍 $(a_1, b_1)$과 $(a_2, b_2)$로 나타낼 수 있습니다. 이때 $|a_1 - a_2| \le 1$, $|b_1 - b_2| \le 1$입니다.
* 편의상 $(a_1, b_1)$과 $(a_2, b_2)$가 나타내는 정점의 집합을 각각 $U$와 $V$라고 합시다.
* $a_1 \ge a_2$, $b_1 \ge b_2$일 경우, $V$에 속하는 모든 정점을 같은 이동 방향에 있는 $U$의 정점과 매칭시킬 수 있습니다. 따라서 이때 최대 이분 매칭은 $a_2 b_2$입니다.
* 대칭성에 의해 $a_1 \le a_2$, $b_1 \le b_2$인 경우도 마찬가지입니다.
* $a_1 > a_2$, $b_1 < b_2$ 또는 그 반대인 경우, 그래프를 그리고 대각선의 한쪽 방향을 골라 그 방향으로 연결된 정점들을 살펴보면 다음의 사실을 관찰할 수 있습니다.
  * 각 대각선 상에는 $U$에 속한 정점과 $V$에 속한 정점이 번갈아서 나타납니다.
  * $a_1 = b_2$, $a_2 = b_1$인 경우에는 각 대각선의 길이가 모두 짝수이며, 아닌 경우에도 가장 긴 대각선의 길이를 제외한 모든 길이는 짝수입니다.
  * 따라서, 이 대각선 방향을 따라 정점의 수가 같거나 적은 쪽 집합에 속한 모든 정점을 반대쪽 집합의 정점과 매칭할 수 있습니다.
* 결과적으로, 하나의 연결 요소의 최대 이분 매칭은 항상 $\min(|U|, |V|)$와 같습니다.
* 지금까지의 모든 결과를 종합하면 하나의 테스트 케이스에 대한 답을 $\mathcal{O}(1)$에 구할 수 있습니다.

제3회 초콜릿컵 - I - Editorial

## 풀이

* $N$번 개구리가 한별랜드에 가장 먼저 입장하려면, $1$번부터 $N-1$번까지의 개구리들은 $N$번 개구리가 모두를 뛰어넘을 수 있도록 공간을 두고 배치되어야 합니다. 구체적으로, 연속한 두 개의 징검다리에 개구리가 있으면 안됩니다.
* 이를 위해서는 최대 약 절반의 징검다리를 사용할 수 있으므로, 개구리들을 2마리씩 짝지어서 2칸 간격으로 세우고, $N$을 입장시키고, 그다음 나머지 개구리들을 입장시키는 방법을 생각할 수 있습니다.
* 개구리 $i$와 $j$가 한 칸에 쌓여 있으면 두 마리 모두를 2칸 앞으로 이동할 수 있지만, 한 칸 앞으로는 이동할 수 없습니다. 따라서 $1$번과 $N$번 징검다리에는 개구리 2마리의 탑을 만들 수 없습니다.
* 또한, 적어도 한 번은 개구리 2마리의 탑이 다른 2마리의 탑을 뛰어넘어야 합니다. 이 때에는 다른 탑의 앞이나 뒤에 2칸의 빈 공간이 필요합니다.

### $N$이 짝수인 경우

* 다음과 같은 구성이 가능합니다.
* $(1, 2)$, $(3, 4)$, $\cdots$, $(N-3, N-2)$번 개구리를 각각 $N-2$, $N-4$, $\cdots$, $2$번 징검다리로 이동시킵니다.
* 맨 뒤에 있는 2칸의 여유 공간을 이용해 $(N-1, N)$번 개구리를 올바른 순서로 도착점으로 이동합니다.
* 이제 $2$번 징검다리에 있는 $(N-3, N-2)$번 개구리를 같은 방법으로 이동하고, 나머지 개구리들을 같은 방법으로 이동합니다.

### $N$이 홀수인 경우

* 먼저 떠오르는 방법은 짝수일 때와 비슷하게 2마리씩 짝지어 옮기고 출발점에 $N$ 하나만 남기는 것일 것입니다.
* 하지만, 그렇게 하면 $(N-2, N-1)$번 개구리들을 올바른 순서로 도착점으로 이동시킬 수 없습니다.
* 이를 살짝 수정하여 다음과 같은 구성이 가능합니다.
* $(1, 2)$, $(3, 4)$, $\cdots$, $(N-4, N-3)$번 개구리를 각각 $N-2$, $N-4$, $\cdots$, $3$번 징검다리로 이동시킵니다.
* $N-2$를 $N$번, $N-1$을 $1$번 징검다리에 놓습니다.
* 이렇게 하면 $N$번 개구리는 2칸씩 뛰어서 비어있는 징검다리만을 이용해 도착점에 갈 수 있습니다.
* 이제 $N-1$과 $N-2$를 순서대로 도착점으로 이동시키면, 나머지 개구리는 짝수일 때와 같은 방법으로 이동할 수 있습니다.

제3회 초콜릿컵 - J - Editorial

## 노트

* 이 문제는 대회 종료 후 지문이 변경되었습니다. 아래 풀이는 변경된 지문을 기준으로 합니다.

## 풀이

* 2단계의 조건을 다른 말로 쓰면, 하나의 단위 조각을 제거한 후 남아있는 초콜릿이 하나의 트리를 이루어야 한다는 뜻이 됩니다.
* 이를 다음과 같이 두 가지로 나누어 순서대로 생각해 봅시다.
  * 남아있는 초콜릿은 하나의 연결 요소를 이루어야 한다.
  * 그 연결 요소는 트리여야 한다.
* 단위 조각을 제거했는데 하나의 연결 요소를 이룬다는 것은, 그 위치가 단절점이 아니라는 것과 동치입니다.
* 따라서, $\mathcal{O}(V+E)$ 단절점 알고리즘을 이용하여 단절점을 모두 찾고, 이들을 답의 후보에서 제거합니다.
* 이제 남은 후보 중에서 제거하면 트리가 되는 점을 고르면 됩니다.
* 전체 그래프의 정점과 간선의 수를 미리 세어 놓고, 정점 $v$를 제거하면 그에 연결된 간선 $\deg(v)$개가 같이 제거되므로, $V-1 = (E-\deg(v)) + 1$인지를 판별하면 됩니다.

제3회 초콜릿컵 - K - Editorial

## 풀이

* 돌리고 뒤집는 연산의 구간 업데이트와 구간 쿼리를 요구하는 문제입니다.
* `R`, `L`, `H`, `V` 연산을 합성해서 나올 수 있는 모든 연산은 총 8가지 연산 (0번 또는 1번 뒤집은 후 0, 1, 2, 또는 3번 한쪽으로 90도 회전) 중 하나가 됩니다.
  * 이때 뒤집는 방향과 돌리는 방향은 어느 쪽으로 하든 상관없고, 풀이의 끝까지 일관되기만 하면 됩니다.
* 편의상 $a$번 뒤집은 후 $b$번 회전하는 연산을 $(a, b)$라고 쓰겠습니다.
* $(a, b)$와 $(c, d)$를 합성한 결과는 다음과 같습니다.
  * $c = 0$인 경우: $(a, (b + d) \operatorname{mod} 4)$
  * $c = 1$인 경우: $(1-a, (d-b) \operatorname{mod} 4)$
* 구간 덮어쓰기 업데이트를 처리하려면, $(a, b)$를 구간의 길이 $x$번만큼 중첩한 결과를 빠르게 구해야 합니다.
* $(a, b)$를 $4$번 중첩하면 $a$와 $b$에 관계없이 원래 상태로 돌아오는 연산, 즉 $(0, 0)$이 됩니다.
* 따라서 $(a, b)$를 $x$번 중첩한 것은 $x \operatorname{mod} 4$번 중첩한 것과 동일하며, 이는 $\mathcal{O}(1)$ 시간에 계산할 수 있습니다.
* 마지막으로, 구간 쿼리의 결과를 가지고 값을 출력할 때에는 배열을 뒤집고 돌리는 대신 주어진 좌표를 역으로 변환한 후 배열의 그 위치의 원소를 출력하면 됩니다.
* 이때, $(a, b)$의 역변환은 $a$번 뒤집은 후 $b$번 반대로 회전하는 것이 아니고, $b$번 반대로 회전한 후 $a$번 뒤집어야 합니다.

제3회 초콜릿컵 - L - Editorial

## 풀이

### 답이 0인 경우와 아닌 경우 판별

* 정삼각형으로 이루어진 격자는 사각 격자와 비슷하게 2색 색칠이 가능합니다.
* 두 색깔의 칸의 수가 서로 다를 경우 정답은 $0$입니다.
* 두 색깔의 칸의 수가 같으려면 $a_1 = a_4$, $a_2 = a_5$, $a_3 = a_6$이어야 함을 증명할 수 있습니다.

### 경우의 수 계산

* 수평인 변을 갖는 아몬드를 수평 아몬드, 그렇지 않은 아몬드를 수직 아몬드라고 합시다. 또한, 수평 아몬드 중에서 정방향의 정삼각형이 왼쪽에 오는 아몬드를 왼쪽 아몬드, 오른쪽에 오는 아몬드를 오른쪽 아몬드라고 합시다.
* 육각형의 윗변에 접한 아몬드는 수평 아몬드입니다. 어떤 수평 아몬드의 아랫변에 접한 아몬드 또한 수평 아몬드입니다.
* 이렇게 수평인 변을 갖는 아몬드를 이어붙여서 하나의 띠로 생각할 수 있습니다.
* 여러 개의 띠는 서로 교차할 수 없으므로, 육각형의 윗변과 아랫변의 단위 구간을 서로 잇는 $a_1$개의 띠가 만들어지게 되고, 각각의 띠는 정확히 $a_2$개의 왼쪽 아몬드와 $a_3$개의 오른쪽 아몬드를 포함합니다.
* 교차하지 않는 $a_1$개의 띠가 고정되면, 나머지 공간을 모두 수직 아몬드로 채울 수 있으며, 그 방법은 유일합니다.
* 따라서, 현재의 띠의 모양이 주어질 때 그 오른쪽에 올 수 있는 띠의 모양을 모두 찾아서 다음 띠의 모양에 대한 경우의 수를 구할 수 있습니다.
* 이미 배치된 6개의 아몬드는 첫 번째와 마지막 띠에만 연관이 있으므로, 초깃값 설정과 최종 합에서 조건에 맞지 않는 상태들을 제거해 주면 됩니다.

### 경우의 수 계산: 별해

* 육각형을 아몬드로 나눈 결과를 살짝 돌려서 잘 보면, $a_1 \times a_2 \times a_3$의 공간에 단위 정육면체를 쌓은 모양으로도 볼 수 있습니다.
* 이렇게 해석할 경우, 하나의 띠의 모양은 $1 \times a_2 \times a_3$의 공간에 쌓인 정육면체의 형태에 대응됩니다.
* 이 형태에서 각 칸 위의 정육면체의 개수는 오른쪽으로 단조증가해야 하고, 앞쪽으로 단조감소해야 함을 알 수 있습니다.
* 이러한 관찰을 바탕으로 DP를 통해 답을 구하면 동일한 답을 얻을 수 있습니다.

## 노트

* 이 문제에서 고정된 아몬드가 없는 경우의 답은 [Mathworld: Plane Partition](https://mathworld.wolfram.com/PlanePartition.html)의 식 8로 아주 간단하게 구할 수 있습니다.

제3회 초콜릿컵 - M - Editorial

## 풀이

### 관찰

* 어떤 상태가 주어질 때, 다음과 같은 특성값을 생각해 봅시다.
  * 주어진 상태의 맨 왼쪽과 오른쪽에 각각 가상의 $HH$가 있다고 가정합니다.
  * 각각의 $H$의 점수는 그 $H$보다 왼쪽에 있는 $T$가 짝수 개이면 $1$, 홀수 개이면 $-1$입니다. 다르게 표현하면, $H$의 왼쪽에 있는 $T$의 개수가 $k$개일 때 $(-1)^k$입니다.
  * $T$의 점수는 모두 $0$입니다.
  * 전체 상태의 특성값은 가상의 $H$를 포함하여 모든 $H$의 점수의 합입니다.
* **Claim:** 현재 상태가 $TT\cdots T$이거나 특성값이 3의 배수이면 패배하고, 그 외의 경우에는 모두 승리합니다.
* 수학적 귀납법으로 증명합니다.
* 먼저 초콜릿의 개수 $N$이 $1$인 경우, $H$에서는 유일한 $H$를 제거하면 승리하고, $T$에서는 아무것도 제거할 수 없으므로 패배합니다. $H$의 특성값은 $5$이며, 이는 3의 배수가 아닙니다.
* 이제 $N = M$에 대해 증명되었다고 가정하고 $N = M+1$인 경우를 증명합니다.
* 양끝이 아닌 곳의 $H$를 제거하는 경우에는 다음과 같이 4가지 경우가 있습니다. $a$와 $b$는 가상의 $H$를 포함한 초콜릿의 배열이며, 제거 전과 후의 특성값을 각각 $S$와 $S'$, $a$와 $b$에 속한 초콜릿의 점수의 합을 각각 $S_a$, $S_b$라고 하고, $a$에 속한 $T$의 개수를 $t_a$라고 합시다.
  * $aHHHb \rightarrow aTTb$: $S = S_a + 3(-1)^{t_a} + S_b$, $S' = S_a + S_b$
  * $aHHTb \rightarrow aTHb$: $S = S_a + 2(-1)^{t_a} + S_b$, $S' = S_a - (-1)^{t_a} + S_b$
  * $aTHHb \rightarrow aHTb$: $S = S_a - 2(-1)^{t_a} + S_b$, $S' = S_a + (-1)^{t_a} + S_b$
  * $aTHTb \rightarrow aHHb$: $S = S_a - (-1)^{t_a} + S_b$, $S' = S_a + 2(-1)^{t_a} + S_b$
* 네 경우 모두 특성값을 3으로 나눈 나머지는 변하지 않습니다.
* 맨 오른쪽 끝의 $H$를 제거하는 경우는 다음과 같습니다. (가상의 $H$는 괄호 안에 표시)
  * $aHH(HH) \rightarrow aT(HH)$: $S = S_a + 4(-1)^{t_a}$, $S' = S_a - 2(-1)^{t_a}$
  * $aTH(HH) \rightarrow aH(HH)$: $S = S_a - 3(-1)^{t_a}$, $S' = S_a + 3(-1)^{t_a}$
* 역시 특성값을 3으로 나눈 나머지는 변하지 않습니다.
* 맨 왼쪽 끝의 $H$를 제거하는 경우는 다음과 같습니다.
  * $(HH)HHb \rightarrow (HH)Tb$: $S = 4 + S_b$, $S' = 2 - S_b$
  * $(HH)HTb \rightarrow (HH)Hb$: $S = 3 + S_b$, $S' = 3 - S_b$
  * 여기서 $S_b$의 부호가 바뀌는 것은 왼쪽의 $T$의 개수의 홀짝이 바뀌기 때문입니다.
* 특성값을 3으로 나눈 나머지는 바뀔 수 있으나, **3의 배수 여부**는 바뀌지 않습니다.
* 따라서, 최초의 특성값이 3의 배수였다면 어떤 $H$를 제거하더라도 특성값은 여전히 3의 배수이므로 귀납적 가정에 의해 패배하게 됩니다.
* 이제, 특성값이 3의 배수가 아니면서 $TT \cdots T$가 아닌 상태에서 $H$를 적절히 제거하면 $TT \cdots T$가 아닌 상태를 유지할 수 있음을 보여야 합니다.
* $H$를 하나 제거하여 $TT \cdots T$를 만들 수 있는 경우는 $HHT \cdots T$, $T \cdots T HHH T \cdots T$, $T \cdots T HH$가 있습니다. 각각에 대해, 전체를 $T$로 만드는 $H$를 제외한 $H$를 아무거나 선택하면 $H$가 하나 이상 존재하도록 할 수 있습니다.
* 그 외의 경우는 $H$를 아무거나 선택해도 $TT \cdots T$가 되지 않습니다.
* 따라서 위의 명제가 성립하고, 귀납적 가정에 의해 승리합니다.

### 계산

* 이제 이 사실을 이용하여 경우의 수 DP를 구성할 수 있습니다.
  * `DP[i][a][b]`: 왼쪽 $i$개의 초콜릿까지 봤을 때, 특성값을 3으로 나눈 나머지가 $a$이고 다음 $H$의 점수가 $b$인 상태의 경우의 수
* 이 DP는 $\mathcal{O} (N)$ 시간에 동작합니다.