2022牛客暑期多校训练营1—I. Chiitoitsu（期望DP）

题目梗概

有种麻将牌，每种牌用一个数字和一个小写字母表示，每种张，共计张；

初始从中摸取张牌；

每次操作从未被摸取过的牌堆中摸取一张；

若此时手中有对牌，则胡牌结束游戏，否则丢出一张牌后继续重复操作，直到胡牌。

给出初始手上的牌，求至少还要多少次操作才能胡牌，结果对取模。

输入形式

输入的第一行为一个正整数 ，表示测试数据的组数；

的

接下来行，每行为一个字符串，长度为，表示初始的张牌。

输出形式

对于第组测试数据，输出一行，格式为“Case #i: x\n”，为结果对取余的数值。

样例

分析

该题为一个期望DP的问题，那么从以下角度分析

用表示牌堆中还有张未被摸取的牌且手上还有张单牌需要凑对时达到胡牌所需要的最小操作步数。

每次摸牌有两种情况

摸到1张新的单牌；

摸到的牌可以和手中的一张牌凑对。

则即可这样分类

当摸到一张新单牌时，则；

摸到的牌可以和手中已有的牌凑对时。

此时可知上述两种情况的概率分别为和，要注意的时时再摸到一张可凑对的牌则直接结束游戏了，即可得到状态转移方程为

还可以化简得到

由题意，初始摸取张牌后牌堆中还剩张牌，设初始手上有张单牌，则答案即为。

C++代码

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

map<string, int> cnt;
int t, dp[150][15];
const int mod = 1e9 + 7;

int ksm(int x, int y, int mod)
{
	int ans = 1, tmp = x;;
	while (y)
	{
		if (y & 1) ans = ans * tmp % mod;
		y >>= 1;
		tmp = tmp * tmp % mod;
	}
	return ans;
}

int inv(int x)
{
	return ksm(x, mod - 2, mod);
}

int dfs(int i, int j)
{ 
	if (dp[i][j] != -1) return dp[i][j];
    if (j == 0) return 0;
    int p1 = (i- 3 * j) * inv(i) % mod;
    int p2 = (3 * j) * inv(i) % mod;
    if(j == 1) dp[i][j] = (p1 * dfs(i - 1, j) + 1) % mod;
    else dp[i][j] = (p1 * dfs(i - 1, j) % mod + p2 * dfs(i - 1, j - 2) % mod + 1) % mod;
    return dp[i][j];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin >> t;
	memset(dp, -1, sizeof(dp));
	int cas = 0;
	while (t--)
	{
		string s;
		cin >> s;
		for (int i = 0; i < 13; i++)
		{
			string c = "";
			c += s[2 * i];
			c += s[2 * i + 1];
			cnt[c]++;
		}
		int n = 0;
		for (auto it : cnt)
		{
			if (it.second == 1) n++;
		}
		cout << "Case #" << ++cas << ": " << dfs(123, n) << endl;
		cnt.clear();
	}
}