同一骨架 2025 年山东预赛 · P006357
把不能同时选的两个位置连成边，合法选择就成为指定大小的独立集。先找冲突图能分解或记忆的局部结构，再分别计各部分容量与方案数；选择对象是位置子集，不额外排列同类棋子或数。
一题的禁差有有限作用距离，可记录最近若干位；另一题的对角接触关系分成小分量，可按分量选取数分类。
培玉 · 一试
2024 年四川预赛
F4填空题组合计数综合
记 ，，集合 的子集 满足
则符合条件的集合 的个数为。（用具体数字作答）
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
先独立尝试，再展开工具说明与想法来源。
想想一道相关的题
先回想这道题的想法，再试试当前题。
思路
状态压缩是用有限位0/1记录最近位置；动态规划把到达同一“未来限制相同”的状态的历史计数相加，本题最多64种窗口，另记选取数。
想法从哪来：逐个挑选五个数会产生很多回溯分支，先问“加入下一个整数时，哪些历史仍会影响合法性”。最大禁差只有六，所以更早的选取情况都可以忘掉，只需记最近六个位置和目前选了几个。每次新数不选与选，分别对应移位后补零或补一；选之前核对的位应由距离减一给出，不能把禁差直接当位号。不同历史即使汇入同一状态也要累加方案数，不能只记录状态是否出现。初始窗口为空，处理满二十五个数后对所有末窗口求和，才能把每个五元集合恰好计一次。直接枚举小规模可帮助检查位序，但不取代转移的穷尽性说明。
禁差只到 ，用记录最近六个整数是否入选的有限状态递推，可无遗漏地计数。
解答
令 表示处理完 后，已选 个数且最近六个数的选取状态为六位掩码 的方案数；最低位表示 是否入选。初值为
加入 时，不选它的转移为
若选它，则因禁差为 ，必须有 的第 位全为 ，此时转移为
逐次递推所得五元集合数如下：
故答案为
复核
每次加入新数时，只需检查与最近 步的数；更早的数差至少为 ，不会违反条件。递推的两类转移互斥且穷尽。
方法总结
有限禁差集合的子集计数适合用“最近最大禁差位”的状态压缩；状态长度由最大禁差决定。
为什么评为 F4（会透露解法方向）
需要把非相邻的四个禁差转为保留最近六个位置的状态，建立无遗漏转移并精确汇总选五个的方案数。
联系 · 1 条
已记下，谢谢！