同一骨架 2026 年北京预赛 · P005966
大规模序列可以按一个位置或完整周期向前处理，只记对下一步有用的完整状态。每一步先列合法转移，再指定初末状态；状态压缩是否正确，应由相同未来行为证明，不能只看当前数值接近。
染色题记录末色并合并对称颜色；数位加法题记录可达进位的集合，还须分清正加数与零加数的边界。
培玉 · 一试
2025 年贵州预赛
奇偶位置限制下的三色染色
F3填空题组合计数综合
一个 的方格表，从左到右依次标上 。现用红、黄、 蓝三种颜色按照如下要求对各小方格分别染色：（1）奇数格可以染红、黄、蓝三种颜色中 任意一种颜色；（2）偶数格只能染红、蓝两种颜色中的一种颜色。且要求相邻的两个格子 不能同色。则该 的方格表的染色方法共有种。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
按“奇数格到下一个奇数格”的两步转移计数。
想想一道相关的题
先回想这道题的想法，再试试当前题。
思路
红、蓝因对称可合并为一个状态，黄色 单列一个状态。
解答
设染到第 个奇数格时，以红色（或蓝色）结尾的方法数为 ，以黄色结尾的 方法数为 。初始 。
在两个相邻奇数格之间有一个偶数格。若下一个奇数格染红色，则此前奇数格染红或黄 各有唯一的中间颜色可选，故
若下一个奇数格染黄，则此前为红、蓝时各有一种选择，此前为黄时有两种选择，故
于是 ，此后 ，所以
全长共有 个奇数格，故染色总数为
复核
长度为 时递推给出 ，直接枚举也为 ；转移已同时计入夹在两奇数 格之间的偶数格颜色，不需额外乘因子。
方法总结
周期性位置具有不同颜色限制时，可按一个完整周期建立状态转移。利用颜色对称合并 状态，能把矩阵递推降为简单的一阶递推。
为什么评为 F3（会透露解法方向）
需要围绕奇数格选择红蓝对称与黄色两个末端状态，跨过偶数格建立两步转移；识别状态固定比例后即转为等比数列。
联系 · 2 条
易混 2025 年广东预赛 · P006231
两题都可把限制转成相邻顶点不能取相同状态，但边界与可用状态集不同。环模型必须让最后与最初也兼容；直线模型没有这条闭合边，却要保留奇偶位置允许颜色不同的信息，不能直接套统一色数的乘方。
前题由禁差关系得到闭环；后题是交替颜色表的开链，递推状态与收尾方式均不同。
已记下，谢谢！