组合计数 - 常见模型

Ex. 1 P5520 青原樱

1. 题面梗概

有多少种方案在 $n$ 个位置种 $m$ 株不同的树，使得树两两不相邻。

$n \leq 2 \times 10^6, m \leq 10^6$

2. 逻辑推导

对于本题来说，直接对着构造取计数看起来会很困难。因此可以考虑使用一些其他的方法来进行解题。

采用插空的方法，由于需要选取 $m$ 个位置种树，因此共有 $n - m$ 个位置不种树。这 $n - m$ 个位置之间有 $n - m + 1$ 个空位，加上两端边界的两个空位，共有 $n - m + 1$ 个空位，只需要将树种在这些空位中即可。

显然，两棵树不可能种在同一个空位中。故最终的答案为 $A_{n-m+1}^{m}$。

Ex.3 P3223 排队

1. 题面梗概

有 $n$ 名男同学，$m$ 名女同学和两名老师要排队。他们排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，那么一共有多少种排法呢？

$n \leq 2000, m \leq 2000$

2. 逻辑推导

同样，这题如果直接用组合数构造符合条件的情况，发现很难表达，不妨采用补集的思路分析：

注意到一共有两个限制条件，“女同学不相邻” ， “老师不相邻”。

那么 “老师不相邻” = 不考虑“老师相邻” - “老师相邻“。

1. 不考虑老师相邻：此时老师和男同学等价，那么通过插空法，即可得到答案为 $A_{n+2}^{n+2} \times C_{n+3}^{m} \times A_{m}^{m}$。

2. 考虑老师相邻：此时可以用捆绑法把两个老师视为一个等价的 “男同学”，即可得到答案：$A_{n+1}^{n+1} \times A_{2}^{2} \times C_{n+2}^{m} \times A_{m}^{m}$。

不过这题还存在一个问题：由于不取模，所以最终的答案会特别大，需要使用高精度，为了方便计算，我们继续化简公式：

$$\begin{align} &Ans = A_{n+2}^{n+2} \times A_{n+3}^{m} - A_{n+1}^{n+1} \times 2 \times A_{n+2}^{m} \\ &Ans = (n+2)! \cdot \frac{(n+3)!}{(n+3-m)!} - (n+1)! \cdot \frac{(n+2)!}{(n+2-m)!} \cdot 2 \\ &Ans = \frac{(n+1)! (n+2)!}{(n+3-m)!} \cdot \left( (n+2)(n+3) - 2(n+3-m) \right) \\ &Ans = \frac{(n+1)! (n+2)!}{(n+3-m)!} \cdot \left( n^2 +3n + 2m \right) \end{align}$$

如此，我们就可以只通过高精度乘法来处理这个答案，代码略。