组合计数问题

steambird · 2024-09-18 14:01:06 · 算法·理论

组合计数问题

组合计数问题和 dp 有相似之处。关于 dp 状态如何设计，可以参考性质与构造相关文章。

技巧

综合

这种问题和 OI 程序题一样需要手动模拟列出部分情况，避免重复/漏解。

人工填表/刷表不要填错位置。容易看错。

子问题划分

组合计数问题中子问题的边界要划分清楚。固定一个答案位置后往往不能换位置。

无序计数

注意，对于每个无序计数，要单独做除法！

轮换对称性

轮换对称的解，依据题意，可能不需要多次计数。

常见错误

（除了忽视了技巧之外的错误）

1. 捆绑法注意内部排列。
2. 注意你状态的最终定义。有些 dp/组合计数状态定义要求在某些位置有额外条件（e.g., “必须选择第 i 个”，在所有位置都可能选择的情况下要求和）
3. 成环要“固定一个”（某一个不能排列）；图上问题还要再固定一个方向（除以 2）。

例题

NOIP 2007 (J/S) R1 第 21 题

首先需要注意从 S(x-1,y), S(x-1, y-1) \to S(x,y)。

先固定 x 的位置。