22牛客多校1 I. Chiitoitsu (概率dp)

传送门

大致题意: 初始手牌13张, 相同牌最多两张, 共34种牌, 每种牌4张, 每次从牌堆摸牌, 要求糊七对, 也就是摸到七对相同牌, 求最优策略下达到七对的轮数

思路: 经典概率dp, 最优策略即上帝视角, 一定不会丢掉已有的单牌(即假定我一定摸到已有单排凑对)

考虑状态dp[i][j], 表示手上有i张单牌, 牌堆中还有j张牌时到达最终状态的轮数

, dp[i][j] = p1*dp[i-2][j-1] + p2*dp[i][j-1] + 1

p1表示从牌堆摸一张牌刚好与手牌中的一张组成对子, 手牌-2 牌堆-1, 概率为 3*i/j

p2 表示从牌堆摸一张牌与手牌没有组成对子, 直接弃牌 手牌不变, 牌堆-1, 概率为(j-3*i)/j

+1 表示摸一张牌

初始化最终状态 dp[1][i] = p*dp[1][i-1] + 1, 只剩一张手牌即游戏结束分界状态时, 从牌堆摸牌, 若凑对则结束, 若没有凑对继续 牌堆-1, 概率为 (i-3)/i,  +1 表示摸一张牌

因为答案取模, 所以考虑乘法逆元代替除法, 用快速幂加速, 代码如下:

#include <bits/stdc++.h>

using namespace std;

stringstream ss;
#define endl "\n"
typedef long long ll;
typedef pair<ll, ll> PII;
typedef pair<pair<int, int>, int> PIII;
const int N = 1e5+10, M = 30, mod = 1e9+7;
const int INF = 0x3f3f3f3f;

int t,T;
int n;
ll dp[20][200]; // dp[i][j] 表示手上有i张单牌, 牌堆中还有j张牌时到达最终状态的期望

ll qmi(ll a, ll k)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = res * a % mod;
        k>>=1;
        a = a*a % mod;
    }
    return res;
}

void solve()
{
    map<string,int> mp;
    string s;
    cin >> s;
    int cnt = 0;
    // 计算初始手牌单牌的数量
    for(int i = 0; i<s.size(); i+=2)
    {
        string str = "";
        str += s[i], str += s[i+1];
        mp[str]++;
    }
    for(int i = 0; i<s.size(); i+=2)
    {
        string str = "";
        str += s[i], str += s[i+1];
        if(mp[str] == 1) cnt++; 
    }
    cout<<"Case #"<<t-T<<": "<<dp[cnt][123]<<endl;
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//    solve();
    // dp[i][j] 表示手上有i张单牌, 牌堆中还有j张牌时到达最终状态的期望
    for(int i = 3; i<=123; i++) // 初始化 dp[1][i] = 1 + (i-3)/i * dp[1][i-1]
    {
        dp[1][i] = (1 + (((i-3)*qmi(i, mod-2) % mod) * dp[1][i-1] % mod)) % mod;
    }

    // 预处理所有值 dp[i][j] = p1*dp[i-2][j-1] + p2*dp[i][j-1] + 1
    // p1 = (3*i)/j p2 = (j-3*i)/j; 
    for(int i = 3; i<=13; i+=2)
    {
        for(int j = 3; j<=123; j++)
        {
            dp[i][j] = (1 + (((i*3) * qmi(j, mod-2) % mod) * dp[i-2][j-1]%mod) + (((j-3*i) * qmi(j, mod-2) % mod)*dp[i][j-1]%mod))%mod;
        }
    }
//    int T;
    cin>>T;
    t = T;
    while(T -- )
    {
        solve();
    }
}