牛客2022暑期集训第一场I题 Chiitoitsu 题解

题目大意

一个人自己打麻将（34种牌型，每种4张）。初始抽13张牌，之后抽一张，若胡牌，则结束。否则则弃掉一张。而在此题中，胡牌的牌型只有7个对子，即7对相同的牌（每对之间不同）。保证起始手牌相同的牌不超过2张。

给定起始手牌，求能够胡牌的期望回合数。

题目链接

思路

不难发现，我们只要是弃掉单张的牌，不管弃掉哪一张，对结果都是没有影响的。所以我们的策略就是：只要抽上来的牌无法和手牌中的牌配对，那就弃掉这张抽上来的牌。

假如我们还差三对牌就能胡牌（即6张单牌），那么我们的任务就是从牌堆中抽出来六种牌的任意三种。那么抽一次，抽到和没抽到的概率分别就是：

$$\frac{6 \cdot 3}{remain},\quad \frac{remain - 6 \cdot 3}{remain}$$

$remain$ 代表牌库中剩下牌的数量，而六种牌型每种有三个。

我们用期望dp的方法，写出状态转移方程，设 $f_{i,j}$ 表示还有 $i$ 张单牌，牌库中此时还剩下 $j$ 张牌。那么假如我们抽上来一张能配对的牌，那么此时手中单牌就会减去2（配对一张，弃掉一张）。而无论是否抽到配对的牌，牌库数量都会减去1。那么我们可以写出状态转移方程：

$$f_{i,j} = 1 + \frac{3i}{j} \cdot f_{i-2,j-1} + \frac{j - 3i}{j} \cdot f_{i,j-1}$$

注意题目让用乘法逆元代替。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const long long mod = 1e9 + 7;

long long qpow(long long a, long long b)
{
    long long tmp = 1;
    while(b) {
        if(b & 1)
            tmp = tmp * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return tmp;
}

long long div(long long a)
{
    return qpow(a, mod - 2);
}

long long sum = 34 * 4 - 13;
long long f[15][34 * 4];

int T;
char ch[31];
string s[20];

int main()
{
    for(int j = 3; j <= sum; ++j) {
        for(int i = 1; i <= 13; ++i) {
            if(j < i * 3)
                continue;
            long long now = 3 * i * div(j) % mod;
            if(i == 1)
                f[i][j] = (1 + (f[i][j - 1] * (1LL + mod - now))) % mod;
            else    
                f[i][j] = (1 + (f[i][j - 1] * (1LL + mod - now) % mod) + f[i - 2][j - 1] * now % mod) % mod;
        }
    }
    scanf("%d", &T);
    for (int test = 1; test <= T; ++test) {
        scanf("%s", ch);
        for (int i = 0; i < 13; ++i) s[i] = ch[i * 2], s[i] += ch[i * 2 + 1];
        sort(s, s + 13);
        int duitsu = 0, single = 0;
        for (int i = 0; i < 12; ++i) duitsu += (s[i] == s[i + 1]);
        single = 13 - duitsu * 2;
        printf("Case #%d: %lld\n", test, f[single][sum]);
    }
    return 0;
}