易混 2022 年全国高中数学联赛一试（A2 卷） 第 11 题 · P007241
二元属性编码成状态后，不能只凭“按顺序”就采用只看相邻末项的计数。下一步需要记住多少历史，应由原条件决定：不重复取物要记已访问集合，任意前后指标的禁配则可能强迫整段结构。
前题三位属性的一位变化给立方体边，抽取不放回要求对子集和末点递推；后题约束作用于所有前后位置，须用特殊状态的首次、末次出现位置证明整体分块，不能只查相邻对。
培玉 · 一试
2023 年江西预赛
F4填空题组合计数综合
有 块不同的积木，每块积木的形状为方形或者圆形，颜色为红色或者黄色，印有城市名为南昌或者北京。 从 块不同的积木中按顺序任取 块积木（）， 表示后一次与前一次取出的积木 在形状、颜色、城市名三个方面恰好有两个相同的所有不同取法总数，则 。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
先独立尝试，再展开工具说明与想法来源。
思路
自避路是顶点不重复的有向行走；子集动态规划记录已用集合和末点，把具有相同后续限制的历史计数合并。立方体每点有三个邻点。
想法从哪来：八块积木刚好是三个二元属性的全部组合，因此先编码成三位零一数，而非按颜色和形状分别分类。相邻恰有两项相同等价于恰翻转一位，正是立方体的边；不可重复取积木则是路径不能重复顶点。只记最后一块不够，因为哪些块已经取过会影响后续选择，要连同已用顶点集合一起记状态。每次从未用邻点延伸即可穷尽，或反过来删去末顶点得到递推。八个起点对称，可以固定一个起点算，再乘八；方向是取出顺序的一部分，不能把反向路径合并。最后比较全部允许长度，最长路径数未必最多。
把三种二选一属性编码为三位零一向量。相邻积木恰有两项相同，等价于立方体图中相邻顶点；题目变成计数有向自避路。
解答
用 表示八块积木，两顶点相邻当且仅当恰有一位不同。固定起点 ，对 及 ，令 为从 出发、恰好经过 中各点一次并终止于 的路数。 则
逐层按 使用这一递推，得到固定起点的路数及全部有序取法如下：
例如前三列也可直接核对：第一步有 种选择，此后立即折返被禁止，而三维立方体没有三角形， 故依次为 。由表可知
在 时取得。
复核
递推只从 的相邻末点接入 ，故既不重顶点也不漏计；立方体的八个起点完全对称，所以总数是固定起点数的八倍。
方法总结
多个二元属性自然对应超立方体；“只差一项”对应边，顺序抽取且不重复对应自避路，可用子集动态递推精确计数。
为什么评为 F4（会透露解法方向）
先将三属性编码为立方体顶点，再需跟踪已访问顶点集合避免重复并比较不同长度的全部路径数；后期分支依赖此前形状，不能用固定乘法原理。
联系 · 1 条
已记下，谢谢！