Colorful Domino Tiling

小规模：枚举摆放与染色

若 $NM$ 为奇数，答案为零。否则，每次找到第一个未覆盖格子，将它与右边或下边的格子配成骨牌，可以恰好枚举每种铺法一次。对每种铺法建立骨牌邻接图，顶点表示骨牌，边表示相邻关系。

依次给顶点染色。若已经使用 $c$ 种颜色，就尝试每种不与已染色邻居冲突的旧颜色，再用一个代表颜色表示新颜色，并将结果乘以 $K-c$。这相当于按首次出现顺序规范化颜色名称。子任务 1 最多只有八块骨牌。设骨牌数为 $D$、铺法数为 $L$，保守上界为 $O(LD^2B_D)$ 时间、$O(NM+D^2)$ 空间，其中 $B_D$ 是 Bell 数。

完整解法：轮廓 DP

必要时旋转网格，使宽度为 $W=\min(N,M)$，高度为 $H=\max(N,M)$。按从上到下、每行从左到右的顺序逐格处理。保留每列最近处理过的格子作为轮廓。在处理一个格子前，该列的轮廓元素是它的上邻格，当前行刚处理过的前一个元素是它的左邻格。

每个轮廓格子保存规范化颜色编号，以及是否已与某个处理过的格子配成完整骨牌的一位标记。尚不存在的格子用颜色编号零表示。未完成格子已经有颜色，但之后必须与右边或下边的格子配对。离开轮廓的格子不再与未处理格子相邻，无须额外记住其颜色。

从左到右扫描轮廓，按颜色首次出现顺序编号为 $1,2,3,\ldots$。例如实际颜色 $(7,2,7,5)$ 规范化为 $(1,2,1,3)$。DP 值是由该状态表示的实际染色及摆放方案数。

转移

设新格子的上邻格和左邻格分别为 $U,L$；不存在的邻格忽略。

• 若 $U$ 未完成，就必须现在与新格子配对。新格子复制 $U$ 的颜色并标记为完成；若 $L$ 存在，则必须与 $L$ 异色。将 $U$ 从轮廓中删除。
• 若 $U$ 不存在或已经完成，可以与未完成的 $$ 配对。新格子复制 的颜色；若 存在，则必须与 异色。将 和新格子都标记为完成。

最后一种情况中，若当前轮廓上有 $c$ 种颜色，就逐一尝试合法旧颜色。未出现在轮廓上的颜色都会得到同一个新编号，因此合并成一次转移并乘以 $K-c$。这些颜色也包括过去用过但已经离开轮廓的颜色。应统计当前活跃颜色数，而非历史上使用过的颜色总数。

用新格子替换上方元素，然后重新规范化。初始轮廓为空，计数为一。全部处理完后，只累加轮廓上所有格子均已完成的状态。

正确性

每块骨牌恰好在按行优先顺序处理其第二个格子时完成一次。上方的未完成格子若不立即配对，此后就无法获得搭档，所以第一种转移是强制的。其余情况下，与左边配对或等待未来搭档完整且互斥地覆盖所有可能。新格子已经处理过的邻格只有上方和左方，因此检查这两个邻格即可准确处理全部邻接条件。颜色重命名不改变合法性，乘数 $K-c$ 恢复了新活跃颜色的实际名称选择数。所以每种合法彩色铺法都恰好被计算一次。

状态数与复杂度

颜色相等关系对应集合划分，数量不超过 Bell 数 $B_W$，其中 $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)$，压缩状态不超过 40 位，使用有符号 64 位整数即可。独立验证程序使用容斥展开异色条件，并维护连通分量来计算相同答案。

Solution written by GPT6