DT-Tiling

경계 상태

현재 열보다 왼쪽의 모든 칸을 채운 상태를 생각하자. 가로로 놓인 일자 트로미노의 길이가 $3$이므로, 이미 놓은 타일은 현재 열과 그다음 열에만 남아 있을 수 있다. 이 두 열의 네 칸을 비트마스크로 나타낸다. 비트 $0,1$은 현재 열의 위아래 칸, 비트 $2,3$은 다음 열의 위아래 칸이다.

현재 열에서 가장 위의 빈 칸을 덮는 타일을 하나씩 놓는다. 현재 열이 가득 차면 마스크를 오른쪽으로 $2$비트 이동한다. 항상 첫 번째 빈 칸을 선택하므로 같은 배치를 여러 번 세지 않는다. 시작 마스크는 $0$이고, $N$열을 처리한 뒤 마스크가 $0$인 경우만 답에 포함한다.

도달 가능한 마스크는 $0,1,2,3,5,7,10,11,15$이다. 위아래 대칭인 마스크의 경우의 수는 같다. $n$열을 처리한 뒤의 다음 여섯 값을 정의하자.

• $f_n$: 마스크 $0$의 경우의 수.
• $u_n$: 마스크 $1$의 경우의 수. 마스크 의 경우의 수와 같다.

대칭인 두 마스크의 합이 아니라 한 마스크의 경우의 수를 저장한다. 첫 번째 빈 칸을 덮는 모든 배치를 열거하면 다음 전이를 얻는다.

$$\begin{array}{rl}{\displaystyle f_{n+1}}& {\displaystyle =f_n+v_n,}\\ {\displaystyle u_{n+1}}& {\displaystyle =f_n+u_n+x_n,}\\ {\displaystyle v_{n+1}}& {\displaystyle =f_n+2u_n+2w_n+y_n,}\\ {\displaystyle w_{n+1}}& {\displaystyle =u_n,}\\ {\displaystyle x_{n+1}}& {\displaystyle =f_n+w_n,}\\ \end{array}$$ $$(f_0,u_0,v_0,w_0,x_0,y_0)=(1,0,0,0,0,0).$$

선형 DP와 행렬 거듭제곱

위 전이를 $N$번 계산하면 $O(N)$ 시간, $O(1)$ 공간에 답을 구할 수 있다. 이는 두 번째 서브태스크를 통과한다.

전체 제한에서는 여섯 값을 열벡터로 두고 전이를 $s_{n+1}=Ms_n$으로 나타낸다. 이때

$$M=(\begin{array}{cccccc}1& 0& 1& 0& 0& 0\\ 1& 1& 0& 0& 1& 0\\ 1& 2& 0& 2& 0& 1\\ 0& 1& 0& 0& 0& 0\\ 1& 0& 0& \end{array}$$

이진 거듭제곱으로 $M^N$을 계산하면 시간 복잡도는 $O(6^3\log N)$, 공간 복잡도는 $O(6^2)$이다. 모든 연산은 을 법으로 수행한다.

제공 코드의 점화식

위 행렬은 다음 항등식을 만족한다.

$$M^6=2M^5+3M^3+2M^2+M-I.$$

따라서 $n\geq6$에 대해

$$f_n=2f_{n-1}+3f_{n-3}+2f_{n-4}+f_{n-5}-f_{n-6}.$$

초기값은

$$(f_0,f_1,f_2,f_3,f_4,f_5)=(1,1,2,6,17,43).$$

제공한 선형 풀이는 이 점화식을 순서대로 계산한다. 정해는 $(f_n,f_{n-1},\cdots,f_{n-5})$를 상태로 하는 행렬을 거듭제곱한다. 마이너스 계수는 법에서 을 뺀 값으로 나타내고, 지수는 64비트 정수로 저장해야 한다.

작은 입력의 완전탐색

첫 번째 서브태스크에서는 $2N$칸 전체를 비트마스크에 담고 첫 번째 빈 칸을 덮는 모든 타일을 시도한다. 이미 계산한 점유 마스크의 결과는 저장한다. 항상 왼쪽부터 채우므로 남는 미완성 상태는 경계 근처 두 열로 제한되어, 열마다 상수 개의 상태만 존재한다. 빈 칸을 선형으로 찾는 구현은 $O(N^2)$ 시간과 $O(N)$개의 저장 상태를 사용한다. 제공한 naive는 최대 $40$비트의 전체 보드 마스크를 사용하는 별도 구현이다.

주의할 점

일자와 L자 트로미노를 모두 사용해야 한다. 일자 트로미노를 세로로 놓으면 높이가 $3$이므로 보드에 들어가지 않는다. 빈 보드의 경우의 수 $f_0=1$은 점화식의 초기값으로만 사용하며 입력으로 $N=0$이 주어지지는 않는다.

행렬 원소를 곱하고 더할 때마다 나머지를 취한다. 중간값의 절댓값은 $(10^9+6)^2+(10^9+6)<1.01\cdot10^{18}$이므로 signed 64-bit 정수로 충분하다.

Solution written by GPT