跳转至

Chiitoitsu

题目链接

I-Chiitoitsu_"蔚来杯"2022牛客暑期多校训练营1 (nowcoder.com)">题目链接

题目大意

初始\(13\)张牌，问凑出\(7\)个对子的期望步数是多少

题解

期望DP，令\(f[i,j]\)表示当前\(i\)个对子牌库还有\(j\)张牌时距离胡牌的期望步数，

Note

题目规定了始牌中不可能出现三张相同的牌，因此只会出现单张与对子的情况

若有\(i\)个对子，就有\(13-2*i\)张单牌，接下来考虑抽牌，抽牌导致的结果可能是对子增加，也可能对子不变，但牌库总牌数一定减少，那如何计算对子增加的概率呢?

我们发现，若想要对某张已有单牌凑出对子，当前牌库中该单排的数量一定是三张，想想就知道了，四张？那手牌不可能有，两张？那已经抽到了，又不可能弃掉对子，一张？那显然同两张的情况一致。\(f[i][j]\)转移到\(f[i+1][j]\)的概率就知道了，就是下一次抽到已有单牌的概率，\(f[i][j]\)转移到\(f[i][j-1]\)的概率和凑成对子互补，具体转移方程如下:

  • \(f[i][j]=\frac{(13-2\times i)\times3}{j}f[i+1][j-1]+(1-\frac{(13-2\times i)\times3}{j})f[i][j-1]\)

滚动数组可以优化成一维

代码

 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
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int l = 34 * 4 - 13;
int f[10][150];
int qpow(int a, int n) {
    int res = 1;
    while(n) {
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

void init() {
    memset(f, 0, sizeof(f));
    for(int i = 6; i >= 0; i -- ) {
        for(int j = 0; j <= l; j ++ ) {
            if((13 - 2 * i) > j) continue;
            int p = (13 - 2 * i) * 3 % mod * qpow(j, mod - 2) % mod;
            f[i][j] = p * f[i + 1][j - 1] % mod + (1 - p) * f[i][j - 1] % mod + 1;
            f[i][j] = (f[i][j] % mod + mod) % mod;
        }
    }
}

signed main() {
    int t;
    cin >> t;
    int kk = 0;
    memset(f, -1, sizeof(f)); 
    init();
    while(t -- ) {
        getchar();
        kk ++ ;
        map<pair<char, char>, int> cnt;
        int d;
        char c;
        int a = 0, b = 0;
        for(int i = 1; i <= 13; i ++ ) {
            scanf("%c%c", &d, &c);
            cnt[{d, c}] ++ ;
            if(cnt[{d, c}] == 2) {
                a ++ ;
            } 
        }
        printf("Case #%lld: %lld\n", kk, f[a][l]);
    }
    return 0;
}