题解

思路

已经被初始骨牌使用的行和列不能再参与新骨牌。竖直骨牌占用一对相邻空行和一个空列；水平骨牌占用一个空行和一对相邻空列。

小范围可直接枚举棋盘上每条相邻边是否放骨牌。中等范围可用二进制集合枚举一维路径上的相邻对匹配。满分算法改用路径动态规划统计选择指定数量互不相交相邻对的方案数。

做法

设空行数为 $R$，空列数为 $C$。令 $A_x$ 表示在空行中选出 $x$ 对互不相交相邻行的方案数，$B_y$ 同理表示空列。

在长度为 $L$ 的行或列序列上，令 $dp[i][k]$ 表示只看前 $i$ 个位置并选出 $k$ 个相邻对的方案数。第 $i$ 个位置不参与相邻对时继承 $dp[i-1][k]$；若最后两个位置均为空，也可把它们配成一对，从 $dp[i-2][k-1]$ 转移。

固定新放置 $x$ 块竖直骨牌与 $y$ 块水平骨牌。先选择其相邻行对和相邻列对，再从剩余行中选出 $y$ 个单行、从剩余列中选出 $x$ 个单列，最后分别建立双射。贡献为

枚举 $x,y$ 求和即为答案，$x=y=0$ 自然计入不新增骨牌的方案。

正确性说明

初始放置已完全平衡，因此任何已被覆盖的行或列都不能再被新骨牌使用。反过来，只要每块新竖直骨牌选择一对相邻空行和一个未使用空列，每块新水平骨牌选择一个未使用空行和一对相邻空列，并保证这些选择互不重复，所得放置就仍然完全平衡。

路径动态规划的两种转移分别对应末位置不参与匹配、以及最后两个空位置组成唯一相邻对，所以 $A_x$ 与 $B_y$ 不重不漏地统计相邻行对和列对。固定 $x,y$ 后，组合数选出另一方向的单行或单列，$x!$ 与 $y!$ 建立双射，从而唯一确定所有新骨牌；任意合法扩展也能唯一逆向分解成这些选择。因此公式对每种方案恰计一次，枚举全部 $x,y$ 后得到总答案。

复杂度

路径动态规划为 $O(h^2+w^2)$，枚举两类骨牌数量为 $O(hw)$；空间复杂度为 $O(h^2+w^2)$。