I：Chiitoitsu

由于题目给定了初始手牌中每种牌最多两张，所以初始手牌里面的单牌数量可能有1，3，5，7，9，11，13这几种，我们可以提前预处理这个数量为cnt


定义一个数组dp[i][j]dp[i][j]表示抽取ii次牌之后剩余jj张单牌的概率，那么我们可以得到状态转移方程如下

dp[i][j]=dp[i−1][j]∗124−i−3j124−i+dp[i−1][j+2]∗3∗(j+2)124−i\quad\quad\quad\quad\quad\quad dp[i][j] =dp[i-1][j]*\frac{124-i-3j}{124-i}+dp[i-1][j+2]*\frac{3*(j+2)}{124-i}


其中第一个概率$\frac{124-i-3j}{124-i}$表示第$i$次抽牌没有抽到和手中单牌（其中一种）一样类型的牌，第二个概率$\frac{3*(j+2)}{124-i}$表示第$i$次抽牌抽到了和手中单牌（其中一种）一样类型的牌。

初始化dp[0][cnt] = 1，然后根据递推式求出所有结果。

//最多抽取121次就能胡牌
for(int i = 1; i<=121; i++){
	for(int j = 1;j<=13;j+=2){
		dp[i][j] = (dp[i-1][j]*(124-i-3*j)%mod+dp[i-1][j+2]*(3*j+6)%mod)%mod*ksm(124-i,mod-2)%mod;
	}
}

有了概率，我们就很好求出期望，根据公式可以得到最终结果为

∑i=1121i∗dp[i−1][1]∗3124−i\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\sum_{i=1}^{121}{i*dp[i-1][1]*\frac{3}{124-i}}

for(int i = 1;i<=121;i++){
	ans = (ans + i*dp[i-1][1]*3%mod*ksm(124-i,mod-2) % mod)%mod;
}

tips

这样写最后TLE了，因为复杂度超了，不过可以注意到每个样例都只有cnt这一个参数在变化，我们完全可以提前把所有的cnt对应的答案预处理出来，后续根据不同的cnt直接输出结果即可。

完整代码如下

#include <bits/stdc++.h>
#define ll long long
#define pf(x) cout<<"("<<__LINE__<<")"<<#x<<"="<<x<<endl
using namespace std;
map<int,int> mp;
map<string,int> book;
const ll mod = 1e9+7;
ll dp[150][16];
ll res[15];
ll ksm(ll a,ll b){
	ll res = 1;
	while(b){
		if(b&1) res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}
void init(){
	for(int k = 1;k<=13;k+=2){
	    memset(dp, 0, sizeof dp);
	    dp[0][k] = 1;
	    for(int i = 1; i<=121; i++){
		    for(int j = 1;j<=13;j+=2){
			    dp[i][j] = (dp[i-1][j]*(124-i-3*j)%mod+dp[i-1][j+2]*(3*j+6)%mod)%mod*ksm(124-i,mod-2)%mod;
		    }
	    }
	
	    ll ans = 0;
	    for(int i = 1;i<=121;i++){
		    ans = (ans + i*dp[i-1][1]*3%mod*ksm(124-i,mod-2) % mod)%mod;
	    }
	    res[k] = ans;
	}
}
void solve(int id){
	string s;
	cin >> s;
	int tot = 0;
	book.clear();
	for(int i = 1;i<=34;i++) mp[i] = 0;
	string tmp;
	for(int i = 0 ; i< s.size();i++){
		tmp += s[i];
		if(i&1){
			int k ;
			if(!book[tmp]) book[tmp] = ++tot;
			k = book[tmp];
			mp[k]++;
			tmp ="";
		}
	}
	
	int cnt = 0;
	for(int i = 1;i<=34;i++) if(mp[i] == 1) cnt ++;
	
	cout << "Case #" <<id <<": "<<res[cnt] <<'\n';
	 
	
	
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int t;
    cin >> t;
    for(int _ = 1;_<=t;_++) solve(_);
    

    return 0;
}

总结一下

这道题被卡了好久，主要还是因为自己没有读题，队友题目也没有读明白
不知道初始手牌每种牌最多两张，而且也不知道要按照最优策略打牌
两个条件一少，完全不知道要怎么写