I Chiitoitsu

$II$题期望dp

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

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

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

1. 有$\frac{3(2j-1)}{i}\backslash frac\{3(2j\; -\; 1)\}\{i\}$的概率摸到需要的牌，此后牌堆少一张牌，所需对子少1，即还需摸$f[i-1][j-1]f[i-1][j-1]$次
2. 有$\frac{i-3(2j-1)}{i}\backslash frac\{i-3(2j-1)\}\{i\}$的概率摸到不是所需要的牌，此后牌堆少一张牌，所需对子不变，即还需摸$f[i-1][j]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][j]=\backslash frac\{3(2j\; -\; 1)\}\{i\}(f[i-1][j-1]+1)+\backslash frac\{i-3(2j-1)\}\{i\}(f[i-1][j]+1)$

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

初始时牌堆有$123123$张牌，答案就是在处理完所需对子$kk$后$f[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;
}