牛客 202H 卡牌游戏 题解【概率期望】【递推】

点击量：258

    是一道思路简单的期望题。

目录

题目描述

小贝喜欢玩卡牌游戏。某个游戏体系中共有\(N\)种卡牌，其中\(M\)种是稀有的。小贝每次和电脑对决获胜之后都会有一个抽卡机会，这时系统会随机从\(N\)种卡中选择一张给小贝。普通卡可能多次出现，而稀有卡牌不会被重复抽到。小贝希望收集到\(K\)种稀有卡牌，她想知道期望需要多少次获胜才能实现这个目标。

 

输入输出格式

输入格式：

数据有多组，第一行一个整数\(T\)表示数据组数。

 

每组数据一行，三个整数\(N,M,K\).

 

输出格式：

对于每组数据，输出形如”Case #x: y”，其中\(x\)为这组数据的编号（从\(1\)开始），\(y\)为这组数据的答案。答案的绝对误差或相对误差在\(10^{-6}\)以内都认为是正确的。

 

输入输出样例

样例输入：

2
5 2 1
40 9 5

样例输出：

Case #1: 2.5
Case #2: 28.1146825397

说明

$$1 ≤ T ≤ 100 \\
1 ≤ N ≤ 10^5 \\
1 ≤ M ≤ N \\
1 ≤ K ≤ M$$

题解：

    是看到这题通过率比较高猜到这题应该不难想，推了一会结论。

    发现这里的概率与条件关系不大，只是分子分母在同时变化，那么我们可以把阶段分出来。因为要抽到第一张稀有卡才能去抽第二张，以此类推，因此定义\(f_i\)表示已经抽到\(i-1\)张卡时，再抽到第\(i\)张卡所需要的期望次数。那么知道普通卡是不会减少的，只用管稀有卡是否减少，只有稀有卡减少了总数才会减少。

    因此当已经抽到\(i\)张时，共有\(n-i\)张卡，其中有\(m-i\)个稀有卡。一次就抽中的概率为\(\frac{m-i}{n-i}\)，那么期望抽到的次数为\((\frac{m-i}{n-i}^{-1}=\frac{n-i}{m-i}\)，而无论抽到哪张卡状态都是唯一的，那么每个阶段的期望就都是确定的了。

    而阶段又是分开的，所以我们可以把阶段连续地加起来，答案就是\(\sum_{i=0}^{k-1}\frac{n-i}{m-i}\)了。时间复杂度\(O(Tk)\)

Code：

#include<cstdio>
#include<cstring>
int main()
{
    int T,n,m,k;
    scanf("%d",&T);
    for(int i=1;i<=T;++i)
    {
        scanf("%d%d%d",&n,&m,&k);
        double ans=0.0;
        for(int j=1;j<=k;++j)
            ans=ans+(double)n--/m--;//直接计算
        printf("Case #%d: %.9lf\n",i,ans);
    }
    return 0;
}