Colorful Domino Tiling

작은 입력: 배치와 색칠의 전수검사

$NM$이 홀수이면 답은 $0$이다. 그렇지 않으면 아직 덮이지 않은 첫 칸을 찾아 오른쪽 또는 아래쪽 칸과 도미노로 묶는 탐색으로 모든 배치를 한 번씩 열거할 수 있다. 배치마다 서로 이웃한 도미노를 간선으로 연결한 그래프를 만든다.

이 그래프의 정점에 순서대로 색을 부여한다. 이미 사용한 색이 $c$가지이면 기존 $c$가지 색 중 이웃과 충돌하지 않는 색을 사용하거나, 아직 사용하지 않은 새 색을 사용한다. 새 색의 경우는 하나의 대표 색으로 탐색하고 결과에 $K-c$를 곱한다. 색 이름을 처음 등장한 순서대로 정규화하는 것이다. 서브태스크 1에서는 도미노가 최대 $8$개이므로 충분하다. 도미노 수를 $D$, 배치 수를 $L$이라 할 때 보수적으로 $O(LD^2B_D)$ 시간, $O(NM+D^2)$ 공간이며, $B_D$는 Bell 수이다.

전체 풀이: 경계 DP

격자를 필요하면 회전하여 너비를 $W=\min(N,M)$, 높이를 $H=\max(N,M)$로 둔다. 위에서 아래로, 각 행은 왼쪽에서 오른쪽으로 한 칸씩 처리한다. 각 열에서 가장 최근에 처리한 칸을 경계에 남겨 둔다. 처리 전인 열의 칸은 바로 위쪽 이웃이고, 현재 행에서 직전에 처리한 칸은 왼쪽 이웃이다.

경계의 각 칸에 다음 두 정보를 저장한다.

• 색 이름을 정규화한 번호. 비어 있는 위치는 $0$이다.
• 이미 처리한 칸과 짝을 이루어 도미노가 완성되었는지 나타내는 비트.

미완성 칸은 나중에 처리할 오른쪽 또는 아래쪽 칸과 짝을 이루어야 한다. 색은 이미 정해져 있다. 경계에서 사라진 칸은 미처리 칸과 더 이상 이웃할 수 없으므로 그 색을 따로 기억할 필요가 없다.

색 번호는 경계를 왼쪽부터 읽으며 처음 등장하는 색에 $1,2,3,\ldots$를 붙여 정규화한다. 예를 들어 실제 색이 $(7,2,7,5)$라면 상태에는 $(1,2,1,3)$을 저장한다. DP 값은 그 정규화 상태에 도달하는 실제 색칠과 배치의 수이다.

새 칸을 추가하는 전이

새 칸의 위쪽 이웃을 $U$, 왼쪽 이웃을 $L$이라 하자. 없는 이웃은 무시한다.

• $U$가 미완성이면 반드시 새 칸과 짝지어야 한다. 새 칸은 $U$와 같은 색이고 완성 상태가 된다. $L$이 있다면 그 색과는 달라야 한다. $U$를 경계에서 지운다.
• $U$가 없거나 이미 완성되어 있으면, 미완성인 $L$과 짝지을 수 있다. 새 칸은 $$과 같은 색이어야 하고, 가 있으면 그 색과는 달라야 한다. 과 새 칸을 모두 완성 상태로 바꾼다.

마지막 경우 현재 경계에 서로 다른 색이 $c$개 있으면, 기존 색마다 가능한지 검사한다. 경계에 없는 색은 모두 같은 새 번호를 만들므로 한 번만 전이하고 $K-c$를 곱한다. 이 수에는 과거에 사용했지만 현재 경계에서는 사라진 색도 포함된다. 중요한 것은 지금 경계에 나타나는 색의 수이지, 지금까지 사용한 색의 총수가 아니다.

매번 위쪽 칸을 새 칸으로 교체하고 색 번호를 다시 정규화한다. 처음에는 경계가 비어 있고 값은 $1$이다. 모든 칸을 처리한 뒤 경계의 모든 칸이 완성된 상태의 값만 더한다. 덮지 못한 칸이 남은 상태를 더하면 안 된다.

정당성

각 도미노는 행 우선 순서에서 두 번째 칸을 처리할 때 정확히 한 번 완성된다. 위쪽 미완성 칸은 지금 짝짓지 않으면 이후 파트너를 얻을 수 없으므로 첫 전이는 강제된다. 나머지 두 전이는 왼쪽과 짝짓거나 미래의 칸을 기다리는 모든 가능성을 나눈 것이다. 이전 칸 중 새 칸과 이웃하는 것은 위쪽과 왼쪽뿐이므로, 이 두 이웃의 색을 검사하면 모든 인접 조건을 정확히 검사한다. 색 이름의 치환은 가능성을 바꾸지 않으며, 새 색 전이의 $K-c$배가 실제 이름의 선택 수를 복원한다. 따라서 모든 유효한 배치와 색칠을 중복 없이 센다.

상태 수와 주의점

색의 같고 다름을 나타내는 상태는 집합 분할이다. $W=8$에서 Bell 수는 $B_8=4140$이며, 완성 비트까지 포함한 상한은 $B_W2^W$이다. 색의 동치 관계가 반드시 비교차인 것은 아니다. 예를 들어 네 세로 도미노의 색이 인 배치는 가능하다. 따라서 이 색 정규화 DP의 상태 수를 Catalan 수로 제한하거나 교차 패턴을 제거하면 안 된다.

한 상태에서 색 선택이 $O(W)$개이고 각 정규화에 $O(W)$가 든다. 해시 맵의 평균 상수 시간 접근을 가정하면 시간은 $O(HW\cdot B_W2^W\cdot W^2)$, 추가 공간은 이다. 실제 도달하는 상태만 저장한다. 이 구현은 최대 입력에서 한 단계에 약 개 상태를 유지한다.

모든 개수는 매 연산 후 $P=998\,244\,353$으로 줄인다. 곱셈은 최대 $100(P-1)$, 덧셈은 $2(P-1)$ 이하이다. 압축 상태는 비트 이내이며 signed 64-bit 범위로 충분하다. 독립 검증용 구현은 도미노 간의 다른 색 조건을 포함·배제로 전개하고 연결 성분을 저장하여 같은 답을 계산한다.

Solution written by GPT6