同一骨架 2026 年贵州预赛 · P006012
两题都先固定某一种颜色占据的格子，再只对剩余方格的邻接关系计数。局部禁配可拆成小图，指定颜色的位置关系决定剩余图的形状；最后才把各类位置的完成数合并。
一题指定蓝格数量后用其余三色完成；另一题每色数量均固定，剩余两色还须满足库存，最终再除以等可能总数。
培玉 · 一试
2021 年四川预赛
F4填空题组合计数综合
在一个 的方格表中，若 个小方格中的每一个均被染成红、黄、蓝、紫四种颜色之一， 任意两个有公共边的小方格的染色均不相同，且该方格表中恰有 个小方格染蓝色， 则符合条件的染色方法数种数为。（用具体数字作答）
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
先独立尝试，再展开工具说明与想法来源。
想想一道相关的题
先回想这道题的想法，再试试当前题。
思路
网格的行状态递推仅需记上一行，因为公共边只连接同行相邻格或上下同列格。颜色彼此有名称，图形旋转用于分组计数而不是视为同一个染色。
想法从哪来：“恰好两个蓝格”提示先固定蓝的位置，而非把四种颜色一起递推；这两个格不能相邻，剩余图只需三种有标号颜色正常着色。利用正方形旋转反射可以合并同型位置，但仅凭都叫角格或边中格还不足以断言同数，最好用逐行状态计算核验各代表。每行内部先满足横向不同，再与上一行按同列逐格比较；蓝格删除后相邻限制只保留双方都非蓝的位置。不同蓝位置对应的着色互不重叠，可以直接乘各类数量相加。最后以所有非邻接格对总数核对分类穷尽，并保留颜色标号，不能再除旋转或颜色交换。
先选两个蓝格；它们不能共边。再把蓝格删去，用三种有标号的颜色给剩余方格作正常着色。 利用正方形的对称性，蓝格对只有四类。
解答
两个蓝格不能共边。 个格子共有 对，其中共边的有 对， 所以可选的蓝格对共有 对。按正方形的旋转、反射对称性，它们分为下表四类：
说明表中最后一列的计算方法。以 表示已选的两个蓝格；逐行染色，令 为第 行所有横向相邻不同的三色状态（蓝格位置记作 ）。 对 定义 ，并递推
最后求和 。分别代入四类代表位置
即依次得到表中的 ；相对边中格给出的数同为 。 因此总数为
复核
四类蓝格对数之和为 ，与 相符；逐行递推同时检查横向、纵向相邻限制。
方法总结
网格恰用若干个指定颜色时，先固定这些格子，再按对称轨道分类；剩余图的着色数可用逐行状态转移复核。
为什么评为 F4（会透露解法方向）
先按24个不相邻蓝格对分类，再对删去蓝格后的不同结构精确统计三色相邻约束；不能只用全格染色数乘选位数。
联系 · 1 条
已记下，谢谢！