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$ 位表示整块棋盘，独立于递推实现。

两种三格骨牌都不能遗漏。竖放的直条形三格骨牌高度为 $3$，不能放入棋盘。空棋盘的计数 $f_0=1$ 只用于初值，输入不包含 $N=0$。

每次乘加后取模，中间值不超过 $(10^9+6)^2+(10^9+6)<1.01\cdot10^{18}$，因此有符号 位整数足够。

Solution written by GPT