I Chiitoitsu_牛客博客

$I$ 题期望dp

设 $f [i] [j]$ 表示牌堆里剩 $i$ 张牌，还差 $j$ 个对子还需摸多少次

注意还差 $j$ 个对子手里还有 $2 j - 1$ 个单牌，摸到不同于手里的牌，不管是否替换掉手里的牌，牌堆里仍有 $3 (2 j - 1)$ 个是需要的牌

在当前状态考虑摸一次牌，有两种情况

有 $\frac{3(2j - 1)}{i}$ 的概率摸到需要的牌，此后牌堆少一张牌，所需对子少1，即还需摸 $f [i - 1] [j - 1]$ 次
有 $\frac{i-3(2j-1)}{i}$ 的概率摸到不是所需要的牌，此后牌堆少一张牌，所需对子不变，即还需摸 $f [i - 1] [j]$ 次

注意无论是哪种情况，都摸了一次牌

所以有

$f[i][j]=\frac{3(2j - 1)}{i}(f[i-1][j-1]+1)+\frac{i-3(2j-1)}{i}(f[i-1][j]+1)$

注意取模，初值 $f [i] [0] = 0$

初始时牌堆有 $123$ 张牌，答案就是在处理完所需对子 $k$ 后 $f [123] [k]$

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 202;
const int mod = 1000000007;
int T, n;
char s[maxn];
int inv[maxn];
int f[maxn][maxn], num[4][maxn];
void deal (int n)
{
    inv[1] = 1;
    for (int i = 2; i <= n; ++i)    inv[i] =  (-1ll * mod / i * inv[mod % i] % mod + mod) % mod;
}
void solve (int n)
{
    for (int i = 3; i <= n; ++i) 
        for (int j = 1; j <= 7 && 3 * (2 * j - 1) <= i; ++j) {
            f[i][j] = 3ll * (2 * j - 1) * inv[i] % mod * (f[i - 1][j - 1] + 1) % mod;
            f[i][j] = (f[i][j] + 1ll * (i - 3 * (2 * j - 1)) * inv[i] % mod * (f[i - 1][j] + 1) % mod) % mod;
        }
}
int main ()
{
    deal(136);
    solve(136);
    cin >> T;
    for (int k = 1; k <= T; ++k) {
        cin >> s + 1;
        int t = 0;
        for (int i = 1; i <= 26; i += 2) {
            int x = s[i] - '0', cur;
            if (s[i + 1] == 'm') cur = 0;
            else if (s[i + 1] == 'p') cur = 1;
            else if (s[i + 1] == 'z') cur = 2;
            else cur = 3;
            ++num[cur][x];
            if (num[cur][x] == 2)   ++t;
        }
        memset(num, 0, sizeof(num));
        cout << "Case #" << k << ": ";
        cout << f[123][7 - t] << endl;
    }
    return 0;
}