计数问题-从入门到进阶

brucelei658 · 2026-01-20 11:40:58 · 算法·理论

题单涵盖了从NOIP到省选/NOI级别的绝大多数计数类考点。

计数题单

第一板块：基础组合数学与经典原理

（地基：高中数学延伸 + 预处理技巧）

这一板块考察对加法/乘法原理的灵活运用，以及如何快速计算组合数。

• P8865 [NOIP2022] 种花：

• 知识点：乘法原理、前缀和优化。

• 核心：将图形拆解，利用前缀和在 时间内查询某一行/列的方案数。

• P3197 [HNOI2008] 越狱：

• 知识点：快速幂、补集转化（正难则反）。

• 核心：总方案 - 合法方案 。

• P1313 [NOIP2011] 计算系数：

• 知识点：二项式定理、快速幂。

• 核心：直接套用 的通项公式。

• P2822 [NOIP2016] 组合数问题：

• 知识点：杨辉三角递推、二维前缀和。

• 核心：利用递推公式 取模并统计。

• P5520 [yLOI2019] 青原樱：

• 知识点：排列组合、插空法。

• 核心：在 个位置选 个且不相邻的模型（）。

• P3223 [HNOI2012] 排队：

• 知识点：高精度、排列组合（插空法 + 捆绑法）。

• 核心：老师必须相邻（捆绑），男生必须不相邻（插空）。

第二板块：三大经典计数数列

（模型：卡特兰、斯特林、错排）

这是提高组向省选跨越的必修课，考察对经典模型的识别。

1. 卡特兰数 (Catalan)

• P1044 [NOIP2003] 栈：进出栈序列计数（卡特兰数入门）。

• P3200 [HNOI2009] 有趣的数列：

• 核心：偶数位大于奇数位，本质是将数字填入 矩阵，等价于路径计数/括号匹配。

• P2532 [AHOI2012] 树屋阶梯：

• 核心：几何图形划分，通过矩形覆盖转化为卡特兰数通项。

• P1641 [SCOI2010] 生成字符串：

• 核心：折线法/翻折法。这是推导卡特兰数通项公式的核心技巧，解决 的路径问题。

2. 斯特林数 (Stirling Numbers)

• P1287 盒子与球：

• 核心：第二类斯特林数基础（球不同、盒不同、不空）。

• P1655 小朋友的球：

• 核心：高精度 + 第二类斯特林数。

• CF1342E Placing Rooks：

• 核心：棋盘放车问题，转化为第二类斯特林数 排列。

• CF961G Partitions：

• 核心：第二类斯特林数 + 贡献法（每个元素对答案的贡献）。

• CF1278F Cards：

• 核心：虽然是概率期望，但解法是利用第二类斯特林数将幂函数 转化为下降阶乘来求和。

• P4609 [FJOI2016] 建筑师：

• 核心：第一类斯特林数。利用“圆排列”模型解决“能看到多少个建筑”的问题。

3. 错排与特殊数列

• P4071 [SDOI2016] 排列计数：
• 核心：组合数选位置 错排公式 。

第三板块：计数 DP (Dynamic Programming)

（算法：将数学融入状态转移）

涵盖了线性、区间、状压、树形等多种DP在计数中的应用。

• P1077 [NOIP2012] 摆花：基础背包类计数（或生成函数入门）。

• P2679 [NOIP2015] 子串：线性 DP，需多开一维记录“当前字符是否被选中”。

• P7960 [NOIP2021] 数列：数位/状压 DP，涉及二进制进位统计 中 的个数。

• P2051 [AHOI2009] 中国象棋：

• 核心：状压 DP / 轮廓线 DP。利用每行每列最多 2 个炮的性质简化状态。

• P7914 [CSP-S 2021] 括号序列：

• 核心：区间 DP。极度考验状态定义的严谨性（分类讨论 (...), AS, SA 等），防止算重。

• CF1183H Subsequences：

• 核心：子序列计数 DP，利用 last[char] 数组去重。

• P3953 [NOIP2017] 逛公园：

• 核心：图论 + 计数 DP。先跑最短路，再在 DAG（或处理零环）上记忆化搜索 偏差路径。

• P3214 [HNOI2011] 卡农：

• 核心：高难度计数 DP + 容斥。在有限制（元素互异、无序）的集合中选子集。

• P4099 [HEOI2013] SAO：

• 核心：树形 DP。利用拓扑序合并的思想，在树上求解满足偏序关系的排列数。

第四板块：容斥原理与反演

（难点：解决“至少”、“至多”、“恰好”类问题）

这是省选计数题中最强大的工具。

• P1450 [HAOI2008] 硬币购物：

• 核心：完全背包预处理 + 基础容斥（总 - 至少1个超限 + 至少2个超限...）。

• P2567 [SCOI2010] 幸运数字：

• 核心：DFS 生成幸运数 + 容斥原理（LCM 去重）。

• P5505 [JLOI2011] 分特产：

• 核心：排列组合 + 容斥（强制某个人没有分到）。

• P5664 [CSP-S 2019] Emiya 家今天的饭：

• 核心：计数 DP 配合容斥。合法 = 总方案 - 某一列超过一半的非法方案。

• CF451E Devu and his Flowers：

• 核心：广义容斥。带有上界限制的插板法（同 P1450，但 更大）。

• P4859 [Already Nothing]：

• 核心：二项式反演。给定 个关系，转化为“至少 个”，再反演求“恰好 个”。

第五板块：数论计数与高级技巧

（进阶：模运算、Lucas、矩阵、GCD）

• P3807 [模板] Lucas 定理：

• 核心：， 很大， 是小质数。

• P3726 [SHOI2015] 超能粒子炮·改：

• 核心：扩展 Lucas / Lucas 变体。求组合数的前缀和 。

• P2398 [NOI2010] 能量采集：

• 核心：GCD 计数。利用欧拉函数 或莫比乌斯反演 转化 。

• CF1332E Height All the Same：

• 核心：奇偶性计数 + 矩阵快速幂。

• P3228 [HNOI2013] 数列：

• 核心：差分思想 + 组合数学。将序列构造转化为差分数组的组合问题。

第六板块：树上计数问题

这些题目涵盖了树形DP、Prufer序列、矩阵树定理等树上计数的三个主要分支。

1. 树形 DP 与 树上结构 (Tree DP)

这类题目通常不直接套公式，而是考察“在树上进行状态转移”的逻辑。

• P2014 [CTSC1997] 选课

• 核心知识点：树形 DP (树上背包)。

• 详解：虽然是求最大价值，但它是树上计数 DP 的原型（“在子树中选 个节点”的状态设计）。理解它对于做 P2051（象棋）等复杂计数题有迁移作用。

• P2234 [HNOI2002] 营业额统计

• 核心知识点：数据结构（平衡树/链表）。

• 详解：前驱后继的查找。虽然被归类在树形结构训练中，但本质是考察动态维护有序集合的能力。

• P1131 [ZJOI2007] 时态同步

• 核心知识点：树形 DP + 贪心。

• 详解：自底向上的树形 DP，计算将所有叶子节点到根的距离调整一致所需的最小代价。考察对树结构的理解。

• CF1083A The Fair Nut and the Best Path

• 核心知识点：树形 DP。

• 详解：树上最长路径权值计算，涉及状态转移 ，是树上统计类问题的经典模型。

2. Prufer 序列 (无根树计数)

解决“已知度数构造树”或“生成树计数”的核心工具。

• P2290 [HNOI2004] 树的计数

• 核心知识点：Prufer 序列、多重集排列、组合数。

• 详解：已知每个节点的度数 ，求生成树个数。公式为 。需要特判无解情况（如 ）。

• P2624 [HNOI2008] 明明的烦恼

• 核心知识点：Prufer 序列、高精度计算。

• 详解：部分节点度数已知，部分未知。需要推导出结合了组合数和 的混合公式，并实现高精度乘法。

• POJ 2395 Out of Hay

• 核心知识点：最小生成树 (MST)、瓶颈路。

• 详解：求生成树中最大边权的最小值。虽然不是直接计数，但常作为 MST 计数题（如 P4208）的前置思维训练。

3. 矩阵树定理 (Matrix Tree Theorem)

解决任意图的生成树计数问题，通常需要用到高斯消元求行列式。

• P4111 [HEOI2015] 小 Z 的房间

• 核心知识点：矩阵树定理、高斯消元求行列式、模运算。

• 详解：在一个有障碍的网格图中求生成树个数。标准的基尔霍夫矩阵（Kirchhoff Matrix）应用题。

• P2144 [FJOI2007] 轮状病毒

• 核心知识点：矩阵树定理 或 递推找规律 + 高精度。

• 详解：特殊的轮状图生成树计数。既可以用矩阵树定理算，也可以推导出 的递推式。

• SP104 HIGH - Highways (SPOJ)

• 核心知识点：矩阵树定理。

• 详解：给出一个图，求生成树的数量。最纯粹的模板题。

4. 卡特兰数 (Catalan)

二叉树形态计数是卡特兰数的典型应用。

• P1044 [NOIP2003] 栈

• 核心知识点：卡特兰数。

• 详解：进出栈序列等价于二叉树的形态计数（前序遍历固定，中序遍历变化）。

• P3200 [HNOI2009] 有趣的数列

• 核心知识点：卡特兰数、线性筛/质因数分解。

• 详解：将 填入数组满足特定条件，本质是求卡特兰数。难点在于模数 可能不互质，需要用质因数分解的方式计算组合数。

第七板块：图上计数

图上计数（Graph Counting）是图论与组合数学的交叉领域。在提高组到省选的跨度中，它主要分为三类：路径计数（DAG/最短路）、生成树计数（矩阵树定理）、以及基于连通性/环的结构计数。

第一阶段：路径与拓扑计数（DAG 与 最短路）

核心逻辑：利用图的无环性（Topological Sort）或最短路的最优子结构进行 DP。

1. 洛谷 P4017 [NOIP2009 普及组] 最大食物链

• 题目描述：在一个 DAG（有向无环图）中，求有多少条路径是从“入度为0的点”到“出度为0的点”。
• 考点：拓扑排序 + 累加 DP。
• 教练点评：
• 为什么选这道题：虽然是普及组题目，但它是所有图上路径计数的鼻祖。你需要掌握 dp[v] += dp[u] 的拓扑递推写法，这是后续解决复杂 DAG 计数的基础。

2. 洛谷 P1144 最短路计数

• 题目描述：在一个无向无权图中，求从起点到所有点的最短路径有多少条。
• 考点：BFS + 计数原理。
• 教练点评：
• 为什么选这道题：最短路计数是提高组高频考点。关键在于：只有当 dis[v] == dis[u] + 1 时，才能进行方案数累加 cnt[v] += cnt[u]。如果是带权图，则需要用 Dijkstra 配合同样的逻辑（参考 P1608）。

第二阶段：生成树计数（矩阵树定理与 MST）

核心逻辑：解决“有多少种连接方式使得图连通”或“最小生成树有多少种”。

3. 洛谷 P4208 [JSOI2008] 最小生成树计数

• 题目描述：给定一个带权无向图，求其最小生成树（MST）的个数。
• 考点：Kruskal 算法性质 + 矩阵树定理（或小数据暴力）。
• 教练点评：
• 为什么选这道题：这道题揭示了 MST 的一个重要性质：任何 MST 中，权值为 的边的数量是固定的，且这些边形成的连通性状况也是固定的。你需要对每种权值的边分别运用矩阵树定理（或者因为数据小直接搜索）来计算方案，最后乘起来。

4. 洛谷 P4111 [HEOI2015] 小 Z 的房间

• 题目描述：在一个 的网格图中，有些墙被打通了，求生成树的个数。
• 考点：矩阵树定理 (Matrix Tree Theorem) + 高斯消元。
• 教练点评：
• 为什么选这道题：最标准的矩阵树定理模板题。你需要构建 基尔霍夫矩阵 (Kirchhoff Matrix)：度数矩阵 - 邻接矩阵，然后求其 阶主子式的行列式值。这是省选图论计数的必修课。

第三阶段：环与连通性计数

核心逻辑：利用 Tarjan 算法处理点双/边双连通分量，或者统计特定长度的环。

5. 洛谷 P1989 无向图三元环计数

• 题目描述：给定一个无向图，求图中“三角形”（三个点两两相连）的个数。
• 考点：根号算法 / 度数定向。
• 教练点评：
• 为什么选这道题：暴力找环是 或 的，这道题考察一种经典优化：将无向边定向（度数小的指向度数大的），将时间复杂度优化到 。这种思想在图论计数中常用于处理“小团”结构。

6. 洛谷 P3225 [HNOI2012] 矿场搭建

• 题目描述：在图中建立救援出口，使得删去任意一个点后，剩余所有点都能到达出口。求最少出口数及方案数。
• 考点：割点 (Cut Vertex) + 点双连通分量 (v-DCC) + 分类讨论。
• 教练点评：
• 为什么选这道题：非常经典的图论计数。它不是直接套公式，而是要求你先理解图的结构（割点）。你需要根据点双连通分量中割点的数量（0个、1个、>1个）进行分类乘法计数。这是图论结构分析能力的极佳训练。

第四阶段：综合难题（图论 + 组合数学）

核心逻辑：在复杂的图限制下进行组合推导。

7. 洛谷 P3214 [HNOI2011] 卡农

• 题目描述：从 的所有子集中选出 个子集，使得每个元素在这些子集中出现偶数次，且子集互不相同、非空。
• 考点：计数 DP + 图论建模（思维） + 排列组合。
• 教练点评：
• 为什么选这道题：虽然题目描述是集合，但本质可以理解为图论问题（限制度数为偶数）。这是一道思维难度极高的计数题，需要利用 DP 解决“非空”和“互不相同”的限制，是图论与组合结合的艺术品。

8. 洛谷 P2624 [HNOI2008] 明明的烦恼

• 题目描述：给出部分节点的度数，求生成树的个数。
• 考点：Prufer 序列 + 高精度。
• 教练点评：
• 为什么选这道题：前面提到的树上计数进阶版。当图退化成完全图，或者对度数有限制时，Prufer 序列是解决生成树计数的唯一神器（比矩阵树定理更高效）。