浅谈 OI 中的计数问题

· · 算法·理论

浅谈 OI 中的计数问题

前言（乱写的）

组合数学中的计数问题是算法竞赛中的熟面孔。这类问题看似不足为奇，但在实际求解问题的过程中常常会使同学们无所适从。对于这类问题，往往要先通过构造法描绘出对象的简单数学模型，再借助在计数问题中常用的一些数学原理方可得出所求对象的总方案数或者其范围和总量。

基础知识

首先来浅浅巩固一下基础知识。（其实全是从各种资料中搬运过来的，只是为了水一波字数而已，想看的看看就好）

排列与组合基础

加法原理

完成一个工程可以有 n 类办法，a_i(1 \le i \le n) 代表第 i 类方法的数目。那么完成这件事共有 S=a_1+a_2+\cdots +a_n 种不同的方法。

乘法原理

完成一个工程需要分 n 个步骤，a_i(1 \le i \le n) 代表第 i 个步骤的不同方法数目。那么完成这件事共有 S = a_1 \times a_2 \times \cdots \times a_n 种不同的方法。

排列数

从 n 个不同元素中，任取 m（m\leq n，m 与 n 均为自然数，下同）个元素按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列；从 n 个不同元素中取出 m(m\leq n) 个元素的所有排列的个数，叫做从 n 个不同元素中取出 m 个元素的排列数，用符号 \mathrm A_n^m（或者是 \mathrm P_n^m）表示。

排列的计算公式如下：

\mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} 公式可以这样理解：$n$ 个人选 $m$ 个来排队 ($m \le n$)。第一个位置可以选 $n$ 个，第二位置可以选 $n-1$ 个，以此类推，第 $m$ 个（最后一个）可以选 $n-m+1$ 个，得： $$ \mathrm A_n^m = n(n-1)(n-2) \cdots (n-m+1) = \frac{n!}{(n - m)!} $$ 全排列：$n$ 个人全部来排队，队长为 $n$。第一个位置可以选 $n$ 个，第二位置可以选 $n-1$ 个，以此类推得： $$ \mathrm A_n^n = n(n-1)(n-2) \cdots 3 \times 2 \times 1 = n! $$ 全排列是排列数的一个特殊情况。 #### 组合数 从 $n$ 个不同元素中，任取 $m \leq n$ 个元素组成一个集合，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m \leq n$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数，用符号 $\dbinom{n}{m}$ 来表示，读作「$n$ 选 $m$」。 组合数计算公式 $$ \dbinom{n}{m} = \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n - m)!} $$ 如何理解上述公式？我们考虑 $n$ 个人选 $m$ 个出来（$m \le n$），不排队，不在乎顺序。如果在乎顺序那么就是 $\mathrm A_n^m$，如果不在乎那么就要除掉重复，那么重复了多少？同样选出来的 $m$ 个人，他们还要「全排」得 $m!$，所以得： $$ \begin{aligned} \dbinom{n}{m} \times m! &= \mathrm A_n^m\\ \dbinom{n}{m} &= \frac{\mathrm A_n^m}{m!} = \frac{n!}{m!(n-m)!} \end{aligned} $$ 组合数也常用 $\mathrm C_n^m$ 表示，即 $\displaystyle \mathrm C_n^m=\binom{n}{m}$。现在数学界普遍采用 $\dbinom{n}{m}$ 的记号而非 $\mathrm C_n^m$。 特别地，规定当 $m>n$ 时，$\mathrm A_n^m=\dbinom{n}{m}=0$。 ### 二项式定理 在进入排列组合进阶篇之前，我们先介绍一个与组合数密切相关的定理——二项式定理。 二项式定理阐明了一个展开式的系数： $$ (a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i $$ 证明可以采用数学归纳法，利用 $\dbinom{n}{k}+\dbinom{n}{k-1}=\dbinom{n+1}{k}$ 做归纳。 二项式定理也可以很容易扩展为多项式的形式： 设 $n$ 为正整数，$x_i$ 为实数， $$ (x_1 + x_2 + \cdots + x_t)^n = \sum_{满足 n_1 + \cdots + n_t=n 的非负整数解} \binom{n}{n_1,n_2,\cdots,n_t} x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t} $$ 其中的 $\dbinom{n}{n_1,n_2,\cdots,n_t}$ 是多项式系数，它的性质也很相似： $$ \sum{\binom{n}{n_1,n_2,\cdots,n_t}} = t^n $$ ## ### 多重集的排列数 | 多重组合数 多重集是指包含重复元素的广义集合。设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$ 表示由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$，…，$n_k$ 个 $a_k$ 组成的多重集，$S$ 的全排列个数为 $$ \frac{n!}{\prod_{i=1}^kn_i!}=\frac{n!}{n_1!n_2!\cdots n_k!} $$ 相当于把相同元素的排列数除掉了。具体地，你可以认为你有 $k$ 种不一样的球，每种球的个数分别是 $n_1,n_2,\cdots,n_k$，且 $n=n_1+n_2+\ldots+n_k$。这 $n$ 个球的全排列数就是 **多重集的排列数**。多重集的排列数常被称作 **多重组合数**。我们可以用多重组合数的符号表示上式： $$ \binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{\prod_{i=1}^kn_i!} $$ 可以看出，$\dbinom{n}{m}$ 等价于 $\dbinom{n}{m,n-m}$，只不过后者较为繁琐，因而不采用。 #### 多重集的组合数 1 设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$ 表示由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$，…，$n_k$ 个 $a_k$ 组成的多重集。那么对于整数 $r(r<n_i,\forall i\in[1,k])$，从 $S$ 中选择 $r$ 个元素组成一个多重集的方案数就是 **多重集的组合数**。这个问题等价于 $x_1+x_2+\cdots+x_k=r$ 的非负整数解的数目，可以用插板法解决，答案为 $$ \binom{r+k-1}{k-1} $$ #### 多重集的组合数 2 考虑这个问题：设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}$ 表示由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$，…，$n_k$ 个 $a_k$ 组成的多重集。那么对于正整数 $r$，从 $S$ 中选择 $r$ 个元素组成一个多重集的方案数。 这样就限制了每种元素的取的个数。同样的，我们可以把这个问题转化为带限制的线性方程求解： $$ \forall i\in [1,k],\ x_i\le n_i,\ \sum_{i=1}^kx_i=r $$ 于是很自然地想到了容斥原理。容斥的模型如下： 1. 全集：$\displaystyle \sum_{i=1}^kx_i=r$ 的非负整数解。 2. 属性：$x_i\le n_i$。 于是设满足属性 $i$ 的集合是 $S_i$，$\overline{S_i}$ 表示不满足属性 $i$ 的集合，即满足 $x_i\ge n_i+1$ 的集合（转化为上面插板法的问题三）。那么答案即为 $$ \left|\bigcap_{i=1}^kS_i\right|=|U|-\left|\bigcup_{i=1}^k\overline{S_i}\right| $$ 根据容斥原理，有： $$ \begin{aligned} \left|\bigcup_{i=1}^k\overline{S_i}\right| =&\sum_i\left|\overline{S_i}\right| -\sum_{i,j}\left|\overline{S_i}\cap\overline{S_j}\right| +\sum_{i,j,k}\left|\overline{S_i}\cap\overline{S_j}\cap\overline{S_k}\right| -\cdots\\ &+(-1)^{k-1}\left|\bigcap_{i=1}^k\overline{S_i}\right|\\ =&\sum_i\binom{k+r-n_i-2}{k-1} -\sum_{i,j}\binom{k+r-n_i-n_j-3}{k-1}+\sum_{i,j,k}\binom{k+r-n_i-n_j-n_k-4}{k-1} -\cdots\\ &+(-1)^{k-1}\binom{k+r-\sum_{i=1}^kn_i-k-1}{k-1} \end{aligned} $$ 拿全集 $\displaystyle |U|=\binom{k+r-1}{k-1}$ 减去上式，得到多重集的组合数 $$ Ans=\sum_{p=0}^k(-1)^p\sum_{A}\binom{k+r-1-\sum_{A} n_{A_i}-p}{k-1} $$ 其中 A 是充当枚举子集的作用，满足 $|A|=p,\ A_i<A_{i+1}$。 #### 圆排列 $n$ 个人全部来围成一圈，所有的排列数记为 $\mathrm Q_n^n$。考虑其中已经排好的一圈，从不同位置断开，又变成不同的队列。 所以有 $$ \mathrm Q_n^n \times n = \mathrm A_n^n \Longrightarrow \mathrm Q_n = \frac{\mathrm A_n^n}{n} = (n-1)! $$ 由此可知部分圆排列的公式： $$ \mathrm Q_n^r = \frac{\mathrm A_n^r}{r} = \frac{n!}{r \times (n-r)!} $$ ### 容斥原理 #### 定义 设 U 中元素有 n 种不同的属性，而第 i 种属性称为 $P_i$，拥有属性 $P_i$ 的元素构成集合 $S_i$，那么 $$ \begin{aligned} \left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\cdots\\ &+(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^{m}S_{a_i}\right|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap S_n| \end{aligned} $$ 即 $$ \left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right| $$ #### 证明 对于每个元素使用二项式定理计算其出现的次数。对于元素 x，假设它出现在 $T_1,T_2,\cdots,T_m$ 的集合中，那么它的出现次数为 $$ \begin{aligned} Cnt=&|\{T_i\}|-|\{T_i\cap T_j|i<j\}|+\cdots+(-1)^{k-1}\left|\left\{\bigcap_{i=1}^{k}T_{a_i}|a_i<a_{i+1}\right\}\right|\\ &+\cdots+(-1)^{m-1}|\{T_1\cap\cdots\cap T_m\}|\\ =&\dbinom{m}{1}-\dbinom{m}{2}+\cdots+(-1)^{m-1}\dbinom{m}{m}\\ =&\dbinom{m}{0}-\sum_{i=0}^m(-1)^i\dbinom{m}{i}\\ =&1-(1-1)^m=1 \end{aligned} $$ 于是每个元素出现的次数为 1，那么合并起来就是并集。证毕。 ### 卡特兰数 以下问题属于 Catalan 数列： 1. 有 $2n$ 个人排成一行进入剧场。入场费 5 元。其中只有 $n$ 个人有一张 5 元钞票，另外 $n$ 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？ 2. 一位大城市的律师在她住所以北 $n$ 个街区和以东 $n$ 个街区处工作。每天她走 $2n$ 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？ 3. 在圆上选择 $2n$ 个点，将这些点成对连接起来使得所得到的 $n$ 条线段不相交的方法数？ 4. 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？ 5. 一个栈（无穷大）的进栈序列为 $1,2,3, \cdots ,n$ 有多少个不同的出栈序列？ 6. $n$ 个结点可构造多少个不同的二叉树？ 7. $n$ 个 $+1$ 和 $n$ 个 $-1$ 构成 $2n$ 项 $a_1,a_2, \cdots ,a_{2n}$，其部分和满足 $a_1+a_2+ \cdots +a_k \geq 0(k=1,2,3, \cdots ,2n)$ 对与 $n$ 该数列为？ 还有一些关于卡特兰数的公式： $$ H_n = \begin{cases} \sum_{i=1}^{n} H_{i-1} H_{n-i} & n \geq 2, n \in \mathbf{N_{+}}\\ 1 & n = 0, 1 \end{cases} $$ $$ H_n = \frac{H_{n-1} (4n-2)}{n+1} $$ $$ H_n = \binom{2n}{n} - \binom{2n}{n-1} $$ ### 第二类斯特林数（Stirling Number） **第二类斯特林数**（斯特林子集数）$\begin{Bmatrix}n\\ k\end{Bmatrix}$，也可记做 $S(n,k)$，表示将 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空子集的方案数。 #### 递推式 $$ \begin{Bmatrix}n\\ k\end{Bmatrix}=\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\ k\end{Bmatrix} $$ 边界是 $\begin{Bmatrix}n\\ 0\end{Bmatrix}=[n=0]$。 考虑用组合意义来证明。 我们插入一个新元素时，有两种方案： - 将新元素单独放入一个子集，有 $\begin{Bmatrix}n-1\\ k-1\end{Bmatrix}$ 种方案； - 将新元素放入一个现有的非空子集，有 $k\begin{Bmatrix}n-1\\ k\end{Bmatrix}$ 种方案。 根据加法原理，将两式相加即可得到递推式。 #### 通项公式 $$ \begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!} $$ 使用容斥原理证明该公式。设将 $n$ 个两两不同的元素，划分到 $i$ 个两两不同的集合（允许空集）的方案数为 $G_i$，将 $n$ 个两两不同的元素，划分到 $i$ 个两两不同的非空集合（不允许空集）的方案数为 $F_i$。 显然 $$ \begin{aligned} G_i&=i^n\\ G_i&=\sum\limits_{j=0}^i\binom{i}{j}F_j \end{aligned} $$ 根据二项式反演 $$ \begin{aligned} F_i&=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}G_j\\ &=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}j^n\\ &=\sum\limits_{j=0}^{i}\dfrac{i!(-1)^{i-j}j^n}{j!(i-j)!} \end{aligned} $$ 考虑 $F_i$ 与 $\begin{Bmatrix}n\\i\end{Bmatrix}$ 的关系。第二类斯特林数要求集合之间互不区分，因此 $F_i$ 正好就是 $\begin{Bmatrix}n\\i\end{Bmatrix}$ 的 $i!$ 倍。于是 $$ \begin{Bmatrix}n\\m\end{Bmatrix}=\dfrac{F_m}{m!}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!} $$ ### 第一类斯特林数（Stirling Number） **第一类斯特林数**（斯特林轮换数）$\begin{bmatrix}n\\ k\end{bmatrix}$，也可记做 $s(n,k)$，表示将 $n$ 个两两不同的元素，划分为 $k$ 个互不区分的非空轮换的方案数。 一个轮换就是一个首尾相接的环形排列。我们可以写出一个轮换 $[A,B,C,D]$，并且我们认为 $[A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]$，即，两个可以通过旋转而互相得到的轮换是等价的。注意，我们不认为两个可以通过翻转而相互得到的轮换等价，即 $[A,B,C,D]\neq[D,C,B,A]$。 #### 递推式 $$ \begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix} $$ 边界是 $\begin{bmatrix}n\\ 0\end{bmatrix}=[n=0]$。 该递推式的证明可以考虑其组合意义。 我们插入一个新元素时，有两种方案： - 将该新元素置于一个单独的轮换中，共有 $\begin{bmatrix}n-1\\ k-1\end{bmatrix}$ 种方案； - 将该元素插入到任何一个现有的轮换中，共有 $(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}$ 种方案。 根据加法原理，将两式相加即可得到递推式。 P.S. 还有很多知识受限于篇幅很难完全讲解清楚（~~其实就是懒得搬运~~），有需要的可以自己去看博客。 ## 例题 一些好玩（~~丧心病狂~~）的例题~ #### P3228 [HNOI2013] 数列 [题目传送门](https://www.luogu.com.cn/problem/P3228) ##### 题目大意 给定四个参数 $N$，$K$，$M$，$P$，你需要构造一个长度为 $K$ 的上升序列，令这个构造序列为 $A$，这个上升序列需要满足以下条件： 1. $\forall A_i,i \in \left\{1 \le i \le k \mid i \in \Z\right\},A_i \le N$。 2. $\forall A_i, i \in \left\{1 < i \le k \mid i \in \Z\right\}, A_{i-1} \le A_i$。 3. $\forall A_i,i \in \left\{1 \le i \le k \mid i \in \Z\right\},A_i - A_{i-1} \le M$。 试求解出构造合法的上升序列 $A$ 的的方案数对 $P$ 取模的结果，其中对于给定的四个参数满足以下条件： 1. $M(K - 1) < N$。 2. $M, K, P \le 10^9, N \le 10^{18}$。 ##### 思路 显然对于每一个合法的上升序列 $A$，这个上升序列对于总方案数的贡献为 $1$，可以考虑维护一个表示序列具体数据的差分序列，这样的话就可以不用考虑 $A_1$ 的取值。 令这个差分序列为 $B$，则 $B$ 的贡献为： $$ n - \sum_{i = 1}^{k - 1}{B_i} $$ 一共会有 $m_{k - 1}$ 个不同的差分序列，总的贡献为： $$ \sum_{i = 1}^{m^{k - 1}}(n - \sum_{j = 1}^{k - 1}{B_{i,j}}) $$ 经过简单变换可得： $$ n \times m^{k - 1} - \sum_{i = 1}^{m^{k - 1}}\sum_{j = 1}^{k - 1}{B_{i,j}} $$ 注意到差分序列 $B_{i,j} \in [1, m]$，显然一共会有 $m^{k - 2} \times (k - 1)$ 个数在 $[1, m]$ 中完全平均分布，则 $[1, m]$ 中的每一个数都会出现 $\frac{m^{k - 1} \times (k - 1)}{m}$ 次。 可以求出总和为： $$ \frac{m^{k - 1} \times (k - 1)}{m} \times \frac{(m + 1)m}{2} $$ 代入原式得： $$ n * m^{k - 1} - \frac{m^{k - 1} \times (k - 1)}{m} \times \frac{(m + 1)m}{2} $$ 经过简单变换可得最终总方案数为： $$ n \times m^{k - 1} - m^{k - 2} \times (k - 1) \times \frac{(m + 1)m}{2} $$ 至于代码实现的话，直接用快速幂和逆元求解这个式子的值就可以了。 具体细节请看代码…… ##### 代码 ```cpp #include <iostream> using namespace std; #define int long long int n, k, m, p, x, y, gcd, ans; int qpow(int a, int b){ int ans = 1; while(b > 0){ if(b & 1){ans *= a;ans %= p;} b >>= 1;a *= a;a %= p; } return ans; } int exgcd(int a, int b, int &x, int &y) // 扩欧求逆元 { if(b == 0){x = 1;y = 0;return a;} int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } signed main(){ cin >> n >> k >> m >> p; gcd = exgcd(2, p, x, y); // 求逆元 x = (x % p + p) % p; ans += (qpow(m, k - 1) * (n % p)) % p; ans -= ((((qpow(m, k - 1) * (k - 1)) % p * (m + 1)) % p) % p * x % p); ans = (ans % p + p) % p; // 依据表达式求解答案 cout << ans << endl; return 0; } // 完结撒花～～ ``` 好好好，题讲完了，下班下班（bushi）。 ## 总结（~~还是乱写的~~） 怎么可能会有总结？但是可以发电。 发个电（诶嘿）： $\texttt{tsqhsaljqrytyybgyqwfyqjyhyfyzjcjbqiulyhhyyxfhwzakioi}$，$\texttt{tsqhsaljqrytyybgyqwfyqjyhyfyzjcjbqiulyhhyyxfhwzakioi}$，$\texttt{tsqhsaljqrytyybgyqwfyqjyhyfyzjcjbqiulyhhyyxfhwzakioi}$，$\texttt{tsqhsaljqrytyybgyqwfyqjyhyfyzjcjbqiulyhhyyxfhwzakioi}$，$\texttt{tsqhsaljqrytyybgyqwfyqjyhyfyzjcjbqiulyhhyyxfhwzakioi}$，$\texttt{tsqhsaljqrytyybgyqwfyqjyhyfyzjcjbqiulyhhyyxfhwzakioi}$，$\texttt{tsqhsaljqrytyybgyqwfyqjyhyfyzjcjbqiulyhhyyxfhwzakioi}$，$\texttt{tsqhsaljqrytyybgyqwfyqjyhyfyzjcjbqiulyhhyyxfhwzakioi}$，$\texttt{tsqhsaljqrytyybgyqwfyqjyhyfyzjcjbqiulyhhyyxfhwzakioi}$，$\texttt{tsqhsaljqrytyybgyqwfyqjyhyfyzjcjbqiulyhhyyxfhwzakioi}$， ……（以下省略 $114514$ 句）