202508 组合计数专题 笔记

总结：放宽限制到好算的地步，再容斥等减去不符合题意的情况。

1. P3862 数圈

题目描述的 $n$ 个点的图，由 $n-1$ 个点的完全图，和一个特殊点组成——这个特殊点只向完全图中连了 $n-2$ 条边。

组成答案的圈有两部分，一部分是完全图中的圈，另一部分是经过特殊点的。

经过特殊点的这一部分，相当于在完全图中选两个点，特殊点再连上这两个点。此时就是要计算这两个点间的路径方案数。

根据完全图的性质，选择哪两个点对路径的方案数没有影响，所以设 $g_i$ 表示在 $i$ 个点的完全图中，$1$ 号点和 $i$ 号点间路径的方案数。

每当添加一个点（$g_{i-1}\to g_i$），可以一步 $1\to i$，也可以 $1\to j\to i$，而 $1\to j$ 的方案数就是 $g_{i-1}$，$j$ 有 $i-2$ 种选择，故

$$g_i=g_{i-1}(i-2)+1$$

完全图中的可以设 $f_i$ 表示 $i$ 个点的完全图中，圈的方案数。

每当添加一个点（$f_{i-1}\to f_i$），相当于 $[1,i-1]$ 点中任选两个组成一条路径，并连上 $i$ 号点，则有转移

$$f_i=f_{i-1}+g_{i-1}\times (\genfrac{}{}{0ex}{}{i-1}{2})$$

最后的答案就是 $f_{n-1}+g_{n-1}\times (\genfrac{}{}{0ex}{}{n-2}{2})$。

时间复杂度 $O(n)$，空间复杂度可做到 $O(1)$。

注意到一组数据中 $\mathrm{\Delta }n$ 不超过 ${10}^6$，花费 $10\mathrm{s}$ 打表出 $n=999,000,000$ 的 $f,g$。

时间复杂度 $O(\mathrm{\Delta }n)$。

2. P3214 [HNOI2011] 卡农

题目要求对同种音乐去重，这相当于多了一个限制，考虑去掉这个限制，最后答案除以 $m!$ 即可。

考虑 DP，设 $f_i$ 表示前 $i$ 个片段音乐均合法的方案数，其中的合法有如下几种限制。

1. 出现的音阶次数都是偶数次。

2. 每个片段都不为空。

3. 没有两个相同的片段。

考虑抛弃后两种限制，用第一种限制进行计数，那只需要任意构造出 $[1,i-1]$ 的片段，让第 $i$ 个片段给他补到对应的偶数次即可。方案数就是构造 $[1,i-1]$ 片段的方案 $A_{2^n-1}^{i-1}$。

接下来考虑去除不符合第二种限制的情况，这说明 $[1,i-1]$ 已经每个音阶都出现偶数次，不需要片段 $i$ 给他补，那就是 $f_{i-1}$ 种方案。

最后考虑限制三，出现相同的片段。观察前面的构造，只有可能是当前的第 $i$ 个片段和前面的某个片段相同。

由于片段相同，同时去掉这两个片段不影响限制一，也就是说剩下的 $i-2$ 个片段合法，即 $f_{i-2}$ 种可能。然后从 $[1,i-1]$ 中任选一个片段出来不合法，$(i-1)$ 种可能，接着从剩下可选的片段集合中选一个出来作为不合法的片段，$2^n-1-(i-2)$ 种可能。

故转移方程

$$f_i=A_{2^n-1}^{i-1}-f_{i-1}-f_{i-2}(i-1)(2^n-1-(i-2))$$

答案为 $f_m$。

时间复杂度 $O(m)$，空间复杂度 $O(m)$。

3. P5376 [THUPC 2019] 过河卒二

先考虑去掉障碍的限制。

考虑传统过河卒：只能向右或向上，从 $(0,0)\to (n,m)$，那就是移动 $n+m$ 步，从中选择 $n$ 步向右，即 $(\genfrac{}{}{0ex}{}{n+m}{n})$。

现在加入了斜着走，因为斜着走移动的步数和向右 / 向上不同，不能简单地组合数计算，需要枚举斜着走的步数，假设斜着走 $i$ 步，那么向右 / 向上就变成了 $(0,0)\to (n-i,m-i)$，而斜着走可以在 $n+m-i$ 个位置中任意选 $i$ 个插入。

$$\sum _{i=0}^{min(n,m)}((\genfrac{}{}{0ex}{}{n+m-2i}{n-i})(\genfrac{}{}{0ex}{}{n+m-i}{i}))$$

对于本题走到任意界外点都算结束，有经典套路将终点向右上方移一格，因为走到新边界后只有一种方案：不断向右或不断向上，不影响答案。

接着考虑加入回障碍的限制，由于障碍数量少，直接二进制枚举进行容斥，对于当前选出来的点的集合，从左往右从上往下排序，计算出相邻两个点间行走的方案数（和上面其实同理），然后相乘即可得出至少经过这些点的方案数。

还需要计算起点到集合中第一个点，和最后一个点到终点的方案。奇负偶正容斥即可。

对于障碍的计算，可以预处理出两两间的方案。

对于这种 $n,m$ 大，模数 $p$ 小的组合数计算，常用 Lucas 定理。

时间复杂度 $O(k^2\times m\times {\log }_{59393}(n)+2^k\times k)$，空间复杂度 $O(59393+k^2)$。