DT-Tiling

境界の状態

現在の列より左側のマスがすべて埋まっている状態を考える。横向きの直線形トロミノの長さは $3$ なので、既に置いたタイルが残るのは現在の列と次の列だけである。この四マスをビットマスクで表し、ビット $0,1$ を現在の列の上下、ビット $2,3$ を次の列の上下に対応させる。

現在の列の最初の空きマスを覆うタイルを置く。列が埋まったらマスクを二ビット右にずらす。常に最初の空きマスを選べば、同じ敷き詰め方を置く順番の違いで重複して数えない。マスク $0$ から始め、$N$ 列を処理した後にマスク $0$ となる場合だけを答えに含める。

到達可能なマスクは $0,1,2,3,5,7,10,11,15$ である。上下対称のマスクの個数は等しい。$n$ 列を処理した時点で、$f_n,u_n,v_n,w_n,x_n,$ をそれぞれマスク の個数とする。マスク と 、 と 、 と の個数はそれぞれ等しい。

対称な二つの合計ではなく、一つのマスクの個数を保持する。最初の空きマスを覆う配置を列挙すると、次の遷移が得られる。

$$\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)$ 空間で計算でき、サブタスク 2 を通過する。全体の制約では六つの値を列ベクトルとし、$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})$ の コンパニオン行列を累乗する。係数 は法から を引いた値で表し、指数には ビット整数を使う。

サブタスク 1 では全 $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}$ 以下であり、符号付き ビット整数で十分である。

Solution written by GPT