【马蹄集】—— 概率论专题：第二类斯特林数

概率论专题：第二类斯特林数

---

MT2224 矩阵乘法

难度：黄金    时间限制：5秒    占用内存：128M

题目描述

输入两个矩阵，第一个矩阵尺寸为 $l\times m$ ，第二个矩阵尺寸为 $m\times n$ ，请你输出这两个矩阵相乘后的结果矩阵。

格式

输入格式：第一行输入三个整数 $l,m$ 和 $n$；
      接下来 $l$ 行，每行 $m$ 个整数，表示第一个矩阵；
     再接下来 $m$ 行，每行 $n$ 个整数，表示第二个矩阵。
输出格式：输出 $l$ 行，每行 $n$ 个整数，表示结果矩阵。

样例 1

输入：
4 3 4
1 2 3
4 -5 6
7 8 9
-3 2 1
4 5 6 7
8 6 9 7
0 0 1 0

输出：
20 17 27 21
-24 -10 -15 -7
92 83 123 105
4 -3 1 -7

备注

其中：$1\le l,m,n\le 1000$，$-1000\le 矩阵中的元素\le 1000$。

相关知识点：线性代数

题解

求解本题只需要知道矩阵乘法的规则即可。设 $A$ 为 $m\times p$ 的矩阵， $B$ 为 $p\times n$ 的矩阵，那么矩阵 $A$ 与 $B$ 可进行乘法运算。设 $C=AB$，则矩阵 $C$ 为一个 $m\times n$ 的矩阵，且 $C$ 的第 $i$ 行第 $j$ 列元素可被表示为：

$$C_{ij}=\sum _{k=1}^p{a}_{ik}{b}_{kj}=a_{i1}{b}_{1j}+a_{i2}{b}_{2j}+\dots +a_{ip}{b}_{pj}$$

如对 $A_{2\times 3}=\left[\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\end{array}\right]$、$B_{3\times 2}=\left[\begin{array}{cc}{b}_{11}& b_{12}\\ b_{21}& b_{22}\\ b_{31}& b_{32}\end{array}\right]$，则有：

$$C_{2\times 2}=AB=\left[\begin{array}{cc}{a}_{11}{b}_{11}+a_{12}{b}_{21}+a_{13}{b}_{31}& a_{21}{b}_{11}+a_{22}{b}_{21}+a_{23}{b}_{31}\\ a_{11}{b}_{12}+a_{12}{b}_{22}+a_{13}{b}_{32}& a_{21}{b}_{12}+a_{22}{b}_{22}+a_{23}{b}_{32}\end{array}\right]$$

下面直接给出求解本题的完整代码：

/*MT2224 矩阵乘法 
*/ #include<bits/stdc++.h> 
using namespace std;const int N = 1005;
int mtx1[N][N], mtx2[N][N];// 输入一个 m*n 的矩阵 
void getMatrix(int m, int n, int matrix[][N])
{for(int i=1; i<=m; i++)for(int j=1; j<=n; j++)cin>>matrix[i][j];
}// 执行矩阵乘法并打印结果 
void matrixMuiti(int l, int m, int n, int matrix1[][N], int matrix2[][N])
{int tmp;for(int i=1; i<=l; i++){for(int j=1; j<=n; j++){tmp = 0;for(int k=1; k<=m; k++)tmp += matrix1[i][k] * matrix2[k][j];cout<<tmp<<" ";}cout<<endl;}
}int main( )
{// 录入数据 int l, m, n;cin>>l>>m>>n;getMatrix(l ,m, mtx1);getMatrix(m, n, mtx2);// 执行矩阵乘法并输出结果matrixMuiti(l, m, n, mtx1, mtx2);return 0;
}

---

MT2231 越狱

难度：钻石    时间限制：1秒    占用内存：128M

题目描述

监狱有 $n$ 个房间，每个房间关押一个犯人，有 $m$ 种宗教，每个犯人会信仰其中一种。如果相邻房间中的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。
答案对1007取模。

格式

输入格式：输入一行只有两个整数，分别代表宗教数 $m$ 和房间数 $n$。
输出格式：输出一行一个整数代表答案。

样例 1

输入：
2 3

输出：
6

备注

其中：$1\le m\le {10}^8，1\le n\le 1010$。

相关知识点：排列组合、快速幂

题解

首先对题目的意思进行简单梳理：有 $n$ 个并排的人（非环形结构），每个人有且仅有一个信仰，现在有 $m$ 种信仰，问相邻两个人具有同一信仰的排列方式有多少种？

“相邻两人具有同一信仰”的排列方式是非常繁杂的，如同信仰的相邻人序列可以取 2、3、……的长度，也可以是中间间隔若干人后出现同信仰的相邻人序列。因此，对这道题采取直接求解法是困难的。此时，我们可以求该事件的对立事件方案数，并用总排列数减去该数即可（总排列数为 $m^n$，第 $i$ 个人有 $m$ 种选择）。

“存在相邻两人具有同一信仰”的对立事件是“任何相邻的人的信仰彼此不同”。在这种情况下，第一个人可以是任意信仰（即 $a_1=m$），接下来第二个人只要不和前一个人信仰相同即可（即 $a_2=m-1$），第三个人同样只需要和其前一个人的信仰不同（即 $a_3=m-1$）……可以发现，后续每个人都只需要满足不和其前一个人的信仰相同即可，即 $a_i=m-1\left(i=2,3,\dots ,n\right)$。于是可得到“任何相邻的人的信仰彼此不同”的排列方案共有 ${\prod }_{i=1}^n{a}_i=m{\left(m-1\right)}^{n-1}$ 种。

所以，“相邻两人具有同一信仰”的排列方案共有 $m^n-m{\left(m-1\right)}^{n-1}$ 种。

从题目给出的数据范围看，所计算的两个值都非常庞大（无标准的数据类型可以存储），因此答案要求对指定数取模。于是这里就涉及到了模运算的一些性质：

• 加法：$\left(a+b\right)\%M=\left(\left(a\%M\right)+\left(b\%M\right)\right)$
• 减法：$\left(a-b\right)\%M=\left(\left(a\%M\right)-\left(b\%M\right)\right)$
• 乘法：$\left(a\times b\right)\%M=\left(\left(a\%M\right)\times \left(b\%M\right)\right)$

从模运算的乘法律可以看出，在计算乘幂时，可以边取余边计算，进而降低中间环节求得的数据范围，使标准数据类型可用。

通过循环求乘幂运算的方法很简单，此处主要探讨快速幂的实现。

幂运算 $m^n$ 有一个特性：每次叠乘时的乘数一致。因此，可通过在已算出的较低次数的乘幂结果上进行新的叠乘运算来降低总计算次数。说简单点就是，$m,m^2,{\left(m^2\right)}^2,\dots$ 直到 $m^n$。这实际上是一种分治的思想，可采用基于递归的方式实现：

int fastPow(int m, int n)
{if(n == 1) return m;int tmp = fastPow(m, n/2);// 幂为奇数 if(n&1) return tmp*tmp*m;// 幂为偶数 else return tmp*tmp;
}

不难看出，采取这种方法实现快速幂的时间复杂度为 $O\left({log}_{2}n\right)$。

另一种基于位运算的快速幂实现方法则从幂的二进制形式出发，通过对幂逐步移位，来实现对幂的分解并完成累乘。例如，对 $m^{11}$，首先将幂转换为二进制得到 ${11}_{10}={1011}_2=2^3+2^1+2^0$，这说明对乘幂 $m^{11}$ 的计算只需要将其幂 11 计算到 3 次即可。下面用一个实际例子予以说明，计算 $m^{11}$（初始化乘幂结果为 $ans=1$，当前底数为 $base=m$）的流程如下：

• 取幂 1011 的末位得到 1 说明当前需要进行一次累乘，于是更新 $ans=ans\ast base=m$。在这之后需要更新底数，于是 $base=base\ast base=m^2$。最后将幂 1011 向右移一个单位得到 101；
• 取幂 101 的末位得到 1 说明当前需要进行一次累乘，于是更新 $ans=ans\ast base=m^3$。在这之后需要更新底数，于是 $base=base\ast base=m^4$ 。最后将幂 101 向右移一个单位得到 10；
• 取幂 10 的末位得到 0 说明当前不需要进行累乘，于是直接更新底数 $base=base\ast base=m^8$。最后将幂 10 向右移一个单位得到 1；
• 取幂 1 的末位得到 1 说明当前需要进行一次累乘，于是更新 $ans=ans\ast base=m^{11}$。在这之后需要更新底数，于是 $base=base\ast base=m^{16}$。最后将幂 1 向右移一个单位得到 0；
• 由于幂已经为 0，故退出算法，输出最终的乘幂结果。

基于位运算的快速幂具有更快的迭代速度，因此在现实中更为常用。下面给出其具体实现（注意，底数 $base$ 可以直接在参数 $m$ 的基础上直接进行变换，而无需单独设置一个变量）：

int fastPow(int m, int n)
{int ans = 1;while(n){if(n&1) ans *= m;// 更新底数m *= m;// 更新幂n >>= 1;}return ans; 
}

对本题而言，由于涉及到的乘幂运算具有较大数据范围，因此需要在求幂的过程中加入取模运算。下面直接给出基于以上思路得到的求解本题的完整代码：

/*MT2231 越狱 排列问题：m^n - m*(m-1)^(n-1)
*/ #include<bits/stdc++.h> 
using namespace std;const int MOD = 1007;// 含取模运算的快速幂模板
int fastPow(long m, long n, long mod)
{m %= mod;int res = 1;while (n){if (n & 1)res = (res * m) % mod;m = (m * m) % mod;n >>= 1;}return res;
}int main( )
{// 录入数据 long m, n;cin>>m>>n;    // 输出结果（注意为了防止出现负数，需要加上 MOD 后再取模）cout<<(fastPow(m, n, MOD)-m*fastPow(m-1, n-1, MOD)%MOD + MOD)%MOD<<endl; return 0;
}

---

MT2232 找朋友

难度：黄金    时间限制：5秒    占用内存：128M

题目描述

将 $n$ 个人分成 $m$ 组，每组至少一人，在比赛结束时，同一组的人两两之间都会成为朋友，不同分组的分组方案得到的朋友对数不同。你的任务是求出最小和最大的朋友对数。

格式

输入格式：两个正整数 $n,m$；

输出格式：两个整数表示答案。

样例 1

输入：

5 1

输出：

10 10

备注

其中：$1\le m\le n\le {10}^9$；

相关知识点：排列组合

题解

题目让我们将 $n$ 个人分进 $m$ 个组中，而在同一个组中的所有人都将成为朋友（即任意两人相互认识）。然后题目的要求是：求在给定人和组数情况下的最小朋友数和最大朋友数。

首先要弄清楚朋友数的含义。例如，$n$ 个人一组时有多少朋友数？实际上，这个问题等价于：$n$ 个顶点最多能形成多少条边？

以某个点为视角，它可以与除自身以外的任何顶点连线得到一条边，因此对这个点而言，它能形成 $n-1$ 条边。一共有 $n$ 个顶点，则一共能形成 $n\left(n-1\right)$ 条边。但是，由于每条边都有两个顶点，因此在按这样的算法（遍历点）统计边数时所有边都会被额外记录一次。所以 $n$ 个顶点最多能形成 $\frac{n\left(n-1\right)}{2}$ 条边。

当然，也可以从排列组合的角度来求解。“$n$ 个顶点最多能形成多少条边”等价于“从 $n$ 个顶点中选择 2 个顶点有多少种选法？”显然，这个问题的答案是 $C_n^2=\frac{n\left(n-1\right)}{2}$。

而本题有所不同，它要求计算将 $n$ 个人分进 $m$ 个组时，整个系统内的最小和最大朋友数。那什么时候系统内的朋友数最少，什么时候又最大呢？前面提到单个组内的人数（假设为 $x$ ）能形成的朋友数为 $\frac{x\left(x-1\right)}{2}$。这是一个关于人数的二次函数，因此其在人数更多的情况下会产生比人数更少时更多的朋友数。所以，为了使整个系统内的朋友数尽可能少，就需要让各个分组内的人数较为平均；为了使整个系统内的朋友数尽可能多，就需要让一个分组得到尽可能多的人，而剩余分组则仅分一人。基于此，可分别有以下结论：

• 最小朋友数：将 $n$ 个人平均分配到 $m$ 个组中。则 $n\%m$ 的组会分到 $\frac{n}{m}+1$ 个人；剩余 $m-n\%m$ 个组将分到 $\frac{n}{m}$（设为 $tmp$）个人。因此，系统内的总朋友数为：$(n\%m)\ast C_{tmp+1}^2+(m-n\%m)\ast C_{tmp}^2$。
• 最大朋友数：将 $m-1$ 个人分到 $m-1$ 个组中（各组一个人），再将剩余 $n-(m-1)$ 个人分至最后一个组中。则前面的 $m-1$ 个组不会产生朋友数，而剩余一个组将产生 $C_{n-(m-1)}^2$个朋友数。

下面给出基于以上思路得到的完整代码：

/*MT2232 找朋友 
*/ 
#include<bits/stdc++.h> 
using namespace std;int main( )
{// 录入数据 int n, m;cin>>n>>m;// 最大的朋友对数 long tmp = n-(m-1);long maxPairs = tmp*(tmp-1)/2;// 最小的朋友对数 tmp = n / m;long minPairs = (m-(n%m))*tmp*(tmp-1)/2 + (n%m)*tmp*(tmp+1)/2;// 输出结果cout<<minPairs<<" "<<maxPairs<<endl; return 0;
}

---

MT2233 盒子与球

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

现有 $r$ 个互不相同的盒子和 $n$ 个互不相同的球，要将这 $n$ 个球放入 $r$ 个盒子中，且不允许有空盒子。请求出有多少种不同的放法。

两种放法不同当且仅当存在一个球使得该球在两种放法中放入了不同的盒子。

格式

输入格式：输入一行只有两个正整数，分别代表 $n$ 和 $r$。
输出格式：输出一行一个整数代表答案。

样例 1

输入：
3 2

输出：

6

备注

其中：$1\le r\le n\le 10$。

相关知识点：排列组合、第二类斯特林数

题解

这是一道经典的盒子放球问题，简化描述如下：$n$ 个不同的球放入 $r$ 个不同的盒子，使每个盒子至少有一个球，问总的放置方案。

有关此类问题的一个总结性帖子：n 球放 m 盒子问题汇总。

这实际上是一个集合划分问题，为解决此类问题定义第二类斯特林数 $\left\{\begin{array}{c}n\\ m\end{array}\right\}$ ，表示将 $n$ 个不同元素划分成 $m$ 个非空集合（读作 “$n$ 子集 $m$”）。由于该定义是将元素分成若干集合，故又将第二类斯特林数称为斯特林子集数。从该定义不难看出这类数的一些特例：

• 当 $n<m$ 时 $\left\{\begin{array}{c}n\\ m\end{array}\right\}=0$。因为总存在集合没有任何元素；
• 当 $n\ge 1$ 时 $\left\{\begin{array}{c}n\\ 1\end{array}\right\}=0$。因为只有一种划分方案，即将所有元素视为一个集合；
• 当 $n=m时$ $\left\{\begin{array}{c}n\\ m\end{array}\right\}=1$。因为只有一种划分方案，即各元素单独形成一个集合；
• 当 $n\ge 2$ 时 $\left\{\begin{array}{c}n\\ 2\end{array}\right\}=2^{n-1}-1$。在这种情况下，可将某一元素视为一个集合 $\mathrm{\Phi }$，其他元素视为另一个集合 $\mathrm{\Omega }$，接下来对集合 $\mathrm{\Phi }$ 中的 $n-1$ 个元素而言，每个元素都有 2 种选择：要么加入集合 $\mathrm{\Phi }$，要么留在集合 $\mathrm{\Omega }$ 中，因此这将产生 $2^{n-1}$ 种组合方案。但是，这里面包含了全部元素都被分至集合 $\mathrm{\Phi }$ 中的情况，因此要再减去 1。

接下来我们讨论第二类斯特林数的递推关系。还是以 “将 $n$ 个元素划分成 $m$ 个非空集合” 为例，假设现在我们要对第 $n$ 个元素进行分配，那么它面对的场景只有两种情况：

• 前面 $n-1$ 个元素形成了 $m-1$ 个集合。在这种情况下，要得到 $m$ 个非空集合就只能将第 $n$ 个元素单独形成一个集合，只有这一种方案，故其总方案数为 $\left\{\begin{array}{c}n-1\\ m-1\end{array}\right\}$。
• 前面 $n-1$ 个元素形成了 $m$ 个集合。在这种情况下，第 $n$ 个元素可任选一个集合加入，共有 $m$ 种选法，故总方案数为 $m\ast \left\{\begin{array}{c}n\\ m\end{array}\right\}$。

于是可得到第二类斯特林数的递推关系：

$$\left\{\begin{array}{c}n\\ m\end{array}\right\}=\left\{\begin{array}{c}n-1\\ m-1\end{array}\right\}+m\left\{\begin{array}{c}n-1\\ m\end{array}\right\}，n\ge 1$$

有了递推关系和初始化条件便能计算第二类斯特林数：

// 第二类斯特林数（递归实现） 
int getStirling(int n, int m)
{if(n<m) return 0;else if((n==m) || (m==1)) return 1;else if(m==2) return pow(2, (n-1))-1;else return getStirling(n-1, m-1) + m*getStirling(n-1, m);
}

注意到一点，本题中的球和盒子都是不同的，而第二类斯特林数仅认定元素之间不同（换言之，用第二类斯特林数计算盒子放球问题时，它得到的结果是盒同而球不同）。为此，我们需要在第二类斯特林数的基础之上再乘以盒子的全排列方案数，即有：

$$m!\left\{\begin{array}{c}n\\ m\end{array}\right\}$$

这便是将 $n$ 个不同球放入 $m$ 个不同盒子的总方案数。

下面给出基于以上思路得到的求解本题的完整代码：

/*MT2233 盒子与球 分球问题、第二类斯特林数 
*/ #include<bits/stdc++.h> 
using namespace std;// 第二类斯特林数（递归实现） 
int getStirling(int n, int m)
{if(n<m) return 0;else if((n==m) || (m==1)) return 1;else if(m==2) return pow(2, (n-1))-1;else return getStirling(n-1, m-1) + m*getStirling(n-1, m);
}
// 阶乘（递归实现）
int getFactorial(int n){if(n==1) return 1;else return n*getFactorial(n-1);
}int main( )
{// 录入数据 int n, r;cin>>n>>r;// 输出结果cout<<getFactorial(r)*getStirling(n, r)<<endl; return 0;
}

---

MT2234 点餐

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

小码哥和他的两个朋友一起去吃饭，他们决定每个人先从菜单上选几道菜，然后点三个人都选中的菜。假设菜单中有 $n$ 道菜，他们三人分别点了 $a,b,c$ 道菜，小码哥想知道是否有可能不存在三个人都选中的菜。

格式

输入格式：一行，4 个以空格分隔的正整数 $n,a,b,c$ 满足 $0<a,b,c\le n\le 1000$。
输出格式：一行，若可能不存三个人都选中的菜就输出 YES，否则输出 NO。

样例 1

输入：
5 3 4 4

输出：

NO

相关知识点：排列组合

题解

求解这道题一定要理解题目所说 “是否有可能不存在三人都选中的菜” 的含义。例如，现在有 5 道菜，三个人分别点了 2、3、4 道菜，则我们需要考虑是否存在一种选菜方案使 “不存在三人都选中的菜” 这种局面出现。例如，一种可能的 “巧合” 如下：

在上面的选菜方案中，没有任何一个菜被三人同时选中，因此对原问题而言，我们的回答是 “YES”。

又比如，现在有 5 道菜，三个人分别点了 2、4、4 道菜，其中有两个人的选菜方案如下：

接下来对第三个人而言，假设他已经知道了另外两个人的选菜方案（具有上帝视角），则为了使 “不存在三人都选中的菜” 这种局面出现，那他就只能选择 “红烧肉” 和 “青菜汤”。

因此对原问题而言，在这样假设下的回答依然是 “YES”。从这里可以看出，原问题是一个 “证存在” 的题设，因此我们在求解时要做的假设是这三个人都足够聪明且足够有默契（相当于直接假设他们彼此可交流）。

注意到一件事，如果给第三个人再多增加一道菜（即现在三人点菜数为 3、4、4），则接下来无论怎样安排每个人的选菜方案，始终会存在某个菜被三人都点一次。即，对原问题回答 “NO”。

可以看出，如果要使得 “不存在三人都选中的菜” 的局面出现，相当于每个菜最多会被点两次。考虑极限情况：即每个菜恰好被点两次。在这种情况下，相当于每个人点的菜的总数之和恰好为总菜品的 2 倍（类似于上图中的情况）。基于此，一旦所有人点的菜的总数之和再多出 1，都会使得某个菜会被点 3 次。因此，不难发现该问题的答案仅取决于 “所有人点的菜的总数之和” 与 “菜品总数” 的大小关系。基于此，可得到求解本题的完整代码：

/*MT2234 点餐 
*/ #include<bits/stdc++.h> 
using namespace std;int main( )
{// 录入数据 int n, a, b, c;cin>>n>>a>>b>>c;// 输出结果 if(a+b+c > 2*n) cout<<"NO"<<endl;else cout<<"YES"<<endl;return 0;
}

END

---