【马蹄集】—— 概率论专题：排列组合

概率论专题：排列组合

---

MT2226 抽奖概率

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

题目描述

小码哥正在进行抽奖，箱子里有一红一白两小球，每次摸出一个球，摸到红球中奖， 如果中奖，就不再继续抽奖；如果未中奖 (摸到白球)，则往箱子里补充一个白球 (摸出的白球不放回)，继续抽奖，直到中奖，或者达到最大抽奖次数。
假设至多能抽奖 $M$ 次，求当停止抽奖时，(中奖球数/摸出总球数) 的期望。

格式

输入格式：一行，一个整数 $M$。
输出格式：保留到小数后六位。

样例 1

输入：
4

输出：
0.682292

备注

其中：$1\le M\le 10000$。

相关知识点：概率论

题解

箱子中只有一个红球和一个白球，因此第一次抽取时，抽到红球和抽到白球的概率各占一半。接下来对该箱子进行盲抽，如果抽出红色则停止抽奖；如果抽到白色则重新放入一个白球（已被抽出的白球不放回）。这就是说，对该箱子的每一次抽取，其内部总是含有一个红球和一个白球。因此这个模型实际上是一个 $p=\frac{1}{2}$ 的伯努利概型。本题要求的，是停止抽奖时 “中奖球数/摸出总球数” 的数学期望。从理论上说，“抽到奖时摸出的总球数” 可以取到无穷大（即永远抽不到）。因此，本题限制假设最多能抽 $M$ 次。

注意到题目要求的是 “中奖球数/摸出总球数” 的期望，而在停止抽奖时（即抽到奖或达到最大抽奖次数时），“中奖球数” 始终为1。因此我们的主要目标是算出停止抽奖时其当前 “摸出的总球数”。显然，这个值可取 1、2、……、M。具体来说，这些取值与其对应的概率如下：

• 抽 1 次中奖的概率：$\frac{1}{2}$（第一次摸到红球），中奖球数/摸出总球数= $\frac{1}{1}$ =1；
• 抽 2 次中奖的概率：$\frac{1}{2}\times \frac{1}{2}=\frac{1}{2^2}$（第一次摸到白球，第二次摸到红球），中奖球数/摸出总球数 = $\frac{1}{2}$ ；
• 抽 3 次中奖的概率：$\frac{1}{2^2}\times \frac{1}{2}=\frac{1}{2^3}$（前两次摸到白球，第三次摸到红球），中奖球数/摸出总球数 = $\frac{1}{3}$ ；
  ……
• 抽 $M$ 次中奖的概率：$\frac{1}{2^{M-1}}\times \frac{1}{2}=\frac{1}{2^M}$（前 $M-1$ 次摸到白球，第三次摸到红球），中奖球数/摸出总球数 = $\frac{1}{M}$ 。

我们知道，离散变量的期望公式为：

$$E\left(X\right)=\sum _{x}x\cdot P(X=x)$$

其中，$P\left(X=x\right)$ 表示变量取 $x$ 时的概率。在本题中， $x$ 的取值范围即为 $\frac{1}{1}$、$\frac{1}{2}$、……、$\frac{1}{M}$，其对应的 $P\left(X=x\right)=\frac{1}{2^x}$。因此本题所求期望的取值即为：

$$E\left(X\right)=\sum _{x}x\cdot P(X=x)=\frac{1}{1}\times \frac{1}{2}+\frac{1}{2}\times \frac{1}{2^2}+\cdots +\frac{1}{M}\times \frac{1}{2^M}$$

基于此，可直接写出求解本题的完整代码：

/*
    MT2226 抽奖概率 
    离散变量的期望公式
*/
#include 
using namespace std; 
// 求“中奖球数 / 摸出总球数” 的期望
float getException(int m){
    int i = 1;
    float ans = 0;
    while(i<=m){
        ans += 1.0/(i*pow(2,i));
        i++;
    }
    return ans;
}
int main()
{
// 获取输入
    int m; cin>>m;
    // 格式化输出期望 
    printf("%.6f",getException(m));
    return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

MT2227 饿饿！饭饭！

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

题目描述

嗯哼，小码哥在新的一年里不会忘记身为干饭人的初心！众所周知，小码哥非常不喜欢一直吃同样的东西，但由于理想与现实的差距，食堂在这 $n$ 天里只会供应种 $k$ 餐食。
在一天吃 3 餐的情况下，前 $w$ 天一共 $w\times 3$ 顿饭小码哥不希望有任何一顿重复。现在请问食堂有多少种方案可以满足超级可爱乖巧的小码哥的需要。

格式

输入格式：一行，三个整数 $n,k,w$ 表示 $n$ 天内食堂只会供应 $k$ 种餐食，$w$ 的意义详见题面。
输出格式：输出一行一个数，表示满足小码哥需要的方案数。

样例 1

输入：
5 4 1

输出：
24

备注

其中：$1\le n,w,k\le 12$。

相关知识点：排列组合

题解

对题目的简化描述如下：食堂提供 $n$ 种餐食，小码哥要吃 $m$ 顿饭，求能使小码哥不吃重的进餐方案数。

这显然是一个排列问题。例如，当 $n=4,m=3$ 时，为使小码哥不吃重，其选择餐食的思路如下：

• 第一顿：小码哥可任意选择餐食，共 4 种方案；
• 第二顿：小码哥只能在剩下 3 种餐食中选择；
• 第三顿：小码哥只能在剩下 2 种餐食中选择。

于是可得到小码哥不吃重的进餐方案数为：4×3×2=24 种。

下面给出排列数的计算公式：

$$A_n^m=n\times \left(n-1\right)\times \dots \times (n-m+1)=\frac{n!}{\left(n-m\right)!}$$

基于此，可得到求解本题的完整代码：

/*
    MT2227 饿饿！饭饭！ 
    排列问题：从 k 个不同物品中选 3*w 个不同物品的方案数 
*/
#include 
using namespace std; 

typedef long long ll;
// 从 n 中选取 m 个物品的排列数 
ll A(ll n, ll m){
    ll ans = 1;
    for(int i=n; m>=1; i--, m--){
        ans *= i;
    }
    return ans;
}

int main()
{
    // 获取输入
    int n,k,w; 
    cin>>n>>k>>w;
    // 格式化输出总方案数
    cout<<A(k,3*w)<<endl; 
    return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

MT2228 甜甜花的研究

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

题目描述

小码哥酷爱研究植物，他对甜甜花的研究无人能及，可他仍然在不断研究着。现在小码哥有 $n$ 粒甜甜花的种子，每一粒种子都能长出不同的甜甜花，由于种子实在太多，小码哥一个人实在无法照料，于是他雇佣了 $m$ 位种植能手，第 $i$ 个人能照料 $a_i$ 株甜甜花，请问小码哥有多少种分配方式将这些种子分配出去？

格式

输入格式：第一行输入以空格隔开的两个整数 $N$ 和 $K$；
     第二行输入 $m$ 个正整数，分别代表 $a_i$。

输出格式：输出一个整数表示方法个数；
     由于结果可能很大，须将结果对 12520 取模。

样例 1

输入：

5 2
3 1

输出：

20

备注

其中：$n\le {10}^4,m\le 100,a_i\le 100$；
数据保证种子有剩余。

相关知识点：排列组合

题解

对题目的简化描述如下：现有 $n$ 粒不同种子，$m$ 个不同盒子（各盒子的容量分别为 $a_1,a_2,\dots ,a_m$）。在保证种子数大于所有盒子容量之和的前提下，问有多少种不同的分装方案。

这显然是一个组合问题。例如，当 $n=8,m=3(a_1=1,a_2=2,a_3=3)$ 时，对这些种子的分装如下：

• 盒子 1：在 $8$ 粒种子中选择 $1$ 粒，共 $C_8^1=8$ 种方案；
• 盒子 2：在剩下 $8-1=7$ 粒种子中选择 2 粒，共 $C_7^2=21$ 种方案；
• 盒子 3：在剩下 $7-2=5$ 粒种子中选择 3 粒，共 $C_5^3=10$ 种方案。

因此总的分装方案数有 8×21×10=1680 种。

下面给出组合数的计算公式：

$$C_n^m=\frac{n\times (n-1)\times \dots \times (n-m+1)}{m\times (m-1)\times \dots \times 1}=\frac{n!}{m!\times (n-m)!}$$

需要注意一点，组合数是一个关于 $n$ 和 $m$ 变化非常大的函数，因此实现时最好采取较大的数据范围和一定的优化方式（如一边除一边乘）。下面直接给出基于以上思路得到的完整代码：

/*
    MT2228 甜甜花的研究
    组合问题 
*/
#include 
using namespace std; 

const int MOD = 12520;
const int M = 105;
int ary[M];

typedef long long ll;
// 从 n 中选取 m 个物品的组合数
ll C(ll n, ll m){
    ll ans = 1;
    for(ll i=1; i<=m; i++){
        // 边乘边除 
        ans = ans*(n-m+i)/i;
    }
    return ans;
}

// 对种子的分配过程 
int Distribute(int n, int m){
    ll ans = 1;
    for(int i=0;i<m; i++){
        ans *= C(n, ary[i]);
        n -= ary[i];
    }
    return ans%MOD;
}

int main()
{
    // 获取输入
    int n, m; cin>>n>>m;
    for(int i=0; i<m; i++)
        cin>>ary[i];
    // 输出期望 
    cout<<Distribute(n, m)<<endl;
    return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

---

MT2229 赌石

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

题目描述

富饶的璃月街道上有一家石料店，店主小码哥是个精明的商人，为了使他的赌石生意更加红火，他根据赌徒的心理设计了一个有趣的买卖规则：他在店铺的两边放了个小桶，一个桶里有 $n$ 个红球，另一个有 $n$ 个蓝球。每一批 $2n$ 个璞石与这些球一一对应，对每个来买璞石的客户，小码哥都会让他们在原地闭眼旋转数圈后走向一个小桶，若拿到蓝球则可免费获得一块石头，但若拿到红球则需要付出两倍的价钱。

假设每个人每次拿到蓝球和红球的概率相同，现在请你求出一个桶里没球而另一个桶里还剩两个球的概率，精确到小数点后四位。

格式

输入格式：输入一个正整数代表这批璞石的个数（不大于2500，且保证为偶数）。
输出格式：输出一个四位小数代表所求答案。

样例 1

输入：
256

输出：

0.9500

相关知识点：排列组合

题解

对题目的简化描述如下：有两个盒子，一个盒子盛有 $n$ 个蓝球，一个盒子盛有 $n$ 个红球。现对这两个盒子进行随机抽取，求最终场上出现一个盒子剩 2 个球，而另一个没有球的概率。

这道题并没有说停止摸球的条件，比如当出现一个盒子没有球，而另一个盒子还剩 3、4、……、$n$ 个球时要如何算？而是直接问出现某种情况的概率。从官方给出的答案看，其对本题模型做出了以下归结：即最终只会存在 3 种情况作为结束时的状态（如下表所示）。

这也就是说，本题默认将 “一个盒子没有球，而另一个盒子还剩 3、4、……、$n$ 个球” 的情形最终归结为 “一个盒子剩 2 个球，另一个没有球” 这种情况。即认为：系统会一直摸球，直到摸到 $2n-2$ 个球为止（当出现某个盒子已经没有球时，下一次摸球就只会从剩余有球的盒子里摸取）。下面我们基于这一设定进行分析。

题目要求的是 “一个盒子剩 2 个球，另一个没有球” 的概率，而从上面的分析可知，这类情况实际上包含了许多状态：即一个盒子没有球，而另一个盒子有2、3、4、……时都为符合要求的状态。这时，可以通过计算这些状态的出现概率（得到通项），然后再以级数的方式进行归结。这种方法有一定的难度，并且过于繁琐。在概率论里，对此类题更常用的处理方式是通过计算对立事件的概率，进而得到原事件的概率。在本题中（从两个各含 $n$ 个球的盒子中随机摸 $2n-2$ 个球），原事件 “一个盒子没有球，而另一个盒子还剩 2 个球” 的对立事件为 “两个盒子各剩下一个球”。于是接下来我们分析 “两个盒子各剩一个球的概率”。

由于摸出球的总数为 $2n-2$ ，如果要求最终两个盒子各剩一个球，那就要求摸出的这 $2n-2$ 个球里，有一半的球来自指定盒子。由于题目说了每个人每次拿到蓝球和红球的概率相等，因此每一次摸球时，此球为蓝色（或红色）的概率是相等的，均为 $\frac{1}{2}$ 。基于此可知：摸出 $2n-2$ 个球里，$n-1$ 个球同色的概率为

$$p=C_{2n-2}^{n-1}{\left(\frac{1}{2}\right)}^{n-1}{\left(\frac{1}{2}\right)}^{n-1}=C_{2n-2}^{n-1}{\left(\frac{1}{2}\right)}^{2n-2}$$

根据该概率值，可以得到其对立事件的概率为：

$$1-p=1-C_{2n-2}^{n-1}{\left(\frac{1}{2}\right)}^{2n-2}$$

这便是本题的答案。

注意到一件事，题目给出的取值范围为 $2n\le 2500$，即 $n$ 最大可取到 1250，这样的范围在求组合数时必定存在过于庞大的数，这意味着即使用 long double 型也可能会越界。因此我们必须简化对该值的求解，即考虑拆分 $C_{2n-2}^{n-1}{\left(\frac{1}{2}\right)}^{2n-2}$ ，使得计算过程能被优化为较小的数之间的四则运算（即找到一个通项式）。

C 2 n − 2 n − 1 ( 1 2 ) 2 n − 2 = ( 2 n − 2 ) ! ( n − 1 ) ! ( n − 1 ) ! × ( 1 4 ) n − 1 = ( 2 n − 2 ) × ( 2 n − 1 ) × … × 1 ( n − 1 ) ! ( n − 1 ) ! × 1 4 n − 1 = ( 2 n − 2 ) × ( 2 n − 1 ) × … × n ( n − 1 ) ! × 1 4 n − 1 = ( 2 n − 2 ) × ( 2 n − 1 ) × … × n 4 n − 1 × [ ( n − 1 ) × ( n − 2 ) × … × 1 ] = ( n − 1 + n − 1 ) × ( n − 1 + n − 2 ) × … × ( n − 1 + 1 ) 4 ( n − 1 ) × 4 ( n − 2 ) × … × 4 ( 1 ) = ∏ i = 1 n − 1 ( n − 1 + i ) 4 i

​C2n−2n−1​(21​)2n−2=(n−1)!(n−1)!(2n−2)!​×(41​)n−1=(n−1)!(n−1)!(2n−2)×(2n−1)×…×1​×4n−11​=(n−1)!(2n−2)×(2n−1)×…×n​×4n−11​=4n−1×[(n−1)×(n−2)×…×1](2n−2)×(2n−1)×…×n​=4(n−1)×4(n−2)×…×4(1)(n−1+n−1)×(n−1+n−2)×…×(n−1+1)​=i=1∏n−1​4i(n−1+i)​​

如此，就将原来求组合数的过程转换为求若干子式（小范围）的乘积。

于是得到 “一个盒子没有球，而另一个盒子还剩2个球” 的概率为：

$$1-\prod _{i=1}^{n-1}\frac{\left(n-1+i\right)}{4i}$$

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

/*
    MT2229 赌石
*/
#include 
using namespace std; 

// 从两个含有 n 个球的桶中取数，最终情况为 0-2 的概率 
double getProbability(int n)
{
    double ans = 1;
    for(int i=1; i<n; i++)
        ans *= (n-1+i)/(i*4.0);
    return 1-ans;
} 

int main()
{
    // 获取输入 
    int n; cin >> n;
    // 格式化输出 
    printf("%.4lf\n", getProbability(n/2));
    return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

MT2230 square

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

题目描述

在一个 $m\times n$ 的矩阵上，小码哥在左下角的顶点出现了，他只能沿着路径向上或者向右走，他的目标是 “蠕动” 到右上角的顶点，问他有多少路径可以选择。嗯，这个、这个、这个似乎地球人都知道怎么做，但是请注意，我有个条件没给呢！$m$ 和 $n$ 现在的最大范围是 50000，这可怎么办？仔细想想吧。

格式

输入格式：只有一行，包含两个整数 $m$ 和 $n$，其均不小于 4，上限均为 50000。
输出格式：由于最后的答案数目过大，所以只检查后 100 位，输出时每行十个数字，没空格间隔，共十行，如果答案位数没超过 100 位，则需要在空位上补 0。

样例 1

输入：
7 4

输出：

0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000330

相关知识点：排列组合

题解

求从矩阵左下角到右上角的行走方案数（每次只能移动一个单位）是一个经典的迷宫问题。解决这个问题最简单的办法是动态规划，因为任意非边缘（这里的边缘主要是指与初始位置相邻的两侧，如本题中就是左侧和下侧）位置的前一个位置必定是左或下，因此可以很轻松地得到状态转移方程为：

$$dp[i][j]=dp[i-1][j]+dp[i][j-1]$$

由于这种行走方式随矩阵规格变化非常剧烈，因此大多数题目都要求记录一个对指定数的模，而本题则要求记录所有行走方式总量的末尾指定长度数串。在这样的要求下，递推求解的思路变得不再适用。
对于走格子矩阵问题（假设其规格为 $m\times n$ ，表示横向有 $m$ 条路径，纵向有 $n$ 条路径），首先要肯定一点：从左下角走到右上角（每次移动一个单位且不可倒退），其一定会走 $m+n$ 步，其中 $m$ 步向右 $n$ 步向上。而各移动方案之间的差异无非就是 “向上” 和 “向右” 的次序不同。例如，对于一个 $2\times 3$ 的矩阵，其行走方案根据 “向上” 和 “向右” 次序的不同，可分为以下 10 种不同的行走方案：

$$\begin{gathered} \to \to \uparrow \uparrow \uparrow \\ \to \uparrow \to \uparrow \uparrow \\ \to \uparrow \uparrow \to \uparrow \\ \to \uparrow \uparrow \uparrow \to \\ \uparrow \to \to \uparrow \uparrow \\ \uparrow \to \uparrow \to \uparrow \\ \uparrow \to \uparrow \uparrow \to \\ \uparrow \uparrow \to \to \uparrow \\ \uparrow \uparrow \to \uparrow \to \\ \uparrow \uparrow \uparrow \to \to \end{gathered}$$

因此，走格子矩阵问题也能通过求组合数得到，此时其含义即为 “在 $m+n$ 步中，选 $n$ 步向上走”（或 “在 $m+n$ 步中，选 $m$ 步向右走”）的总方案数。即 $C_{m+n}^n$ （或 $C_{m+n}^m$）。另一方面，本题中的 $m$ 和 $n$ 最大可取到 5000，这对组合数而言，是一个十分庞大的数据（任何数据类型都无法存储下），就算采取 “边乘边除” 的策略也没有一个数据类型能对中间结果进行存储，因此我们现在的问题是如何实现大范围的组合数求解？

在前面质数章节曾提到，任意一个大于 1 的正整数 $num$ 都可以分解为若干质因数的乘幂之积：

$$num=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times \dots \times p_k^{{\alpha }_k}$$

基于此，我们可将求组合数的过程进行转换：每对一个数进行乘法运算时，不直接算出乘积，而是记录当前乘数可被划分为哪些质因数之积，并对这些质因数进行相应记录。显然，对组合数分子部分的阶乘要累加记录各乘数的质因数，对组合数分母部分的阶乘要累减记录各乘数的质因数。例如，求组合数 $C_{20}^5$ 的过程如下（设质因数数组为 factor[ ]={0}）：

$$C_{20}^5=\frac{20\times 19\times 18\times 17\times 16}{5\times 4\times 3\times 2\times 1}$$

阶段一：统计分子部分的阶乘。

• 分解 $20=2^2\times 5^1$ ，于是有：factor[2]={2}，factor[5]={1}；
• 分解 $19={19}^1$，于是有：factor[19]={1}；
• 分解 $18=2^1\times 3^2$，于是有：factor[2]={3}，factor[3]={2}；
• 分解 $17={17}^1$，于是有：factor[17]={1}；
• 分解 $16=2^4$，于是有：factor[2]={7}。

阶段二：统计分母部分的阶乘。

• 分解 $5=5^1$ ，于是有：factor[5]={0}；
• 分解 $4=2^2$ ，于是有：factor[2]={5}；
• 分解 $3=3^1$ ，于是有：factor[3]={1}；
• 分解 $2=2^1$ ，于是有：factor[2]={4}。

两个阶段结束后，最终得到的质因子数组内容为：factor[3]={1}、factor[5]={1}、factor[17]={1}、factor[19]={1}。将这些质因数按其对应次数进行叠乘，即得到 $C_{20}^4$ 的值：$2^4\times 3^1\times {17}^1\times {19}^1=15504$ 。

采取这样的方式，可将组合数在计算过程中涉及到的阶乘运算巧妙地转换为若干个质因数的乘积过程，从而避免了组合数在大数情况下容易越界的风险。另一方面，如果直接采取大数运算的方式求组合数，会出现大数除法的情况，采取质因数分解的办法可避免出现除法。

由于前面已经给出了 质因数分解 以及 大数乘法 的相关实现，在此就直接给出基于以上思路得到的求解本题目的完整代码：

/*
    MT2230 squre
    求组合数 、质因数分解、大数乘法 
*/
#include 
using namespace std;
const int N = 1e6 + 7;
const int M = 100; 
// 质因数数组 
int factor[N];
// 大数乘法的结果数组
int ans[M+5];
// 大数乘法（单精度*高精度） 
void multi(int x)
{
    // 将原数组中的各数与指定数相乘
    for(int i=1; i<=M; i++)
        ans[i] *= x;
    // 进位处理 
    for(int i = 1; i <= M; i++) {
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
    }
}
int main()
{
    int m, n, x;
    cin>>m>>n;
    // 尽可能减少计算量 
    if(m>n) swap(m, n);
    // 记录 C(m, n) 分子 n*(n-1)*…*(n-m+1) 的质因数 
    for(int i=0; i<m; i++) {
        x= m+n-i;
        for(int j = 2; j<=x/j; j++) {
            while(x%j == 0) {
                x /= j;
                factor[j]++;
            }
        }
        if(x != 1)
            factor[x]++;
    }
    // 记录 C(m, n) 分母 m! 的质因数（约去） 
    for(int i=1; i<=m; i++) {
        x = i;
        for(int j = 2; j<=x/j; j++) {
            while(x%j == 0) {
                x /= j;
                factor[j]--;
            }
        }
        if(x != 1)
            factor[x]--;
    }
    // 遍历保存的质因数，通过大数乘法统计结果 
    ans[1] = 1;
    for(int i=1; i < N; i++) {
        while(factor[i]) {
            multi(i);
            factor[i]--;
        }
    }
    // 格式化输出 
    for(int i=M; i>=1; i--) {
        cout<<ans[i];
        if(i%10 == 1) cout<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

END

---