[数据结构与算法]2022牛客暑期多校训练营1 I Chiitoitsu

2022牛客暑期多校训练营1 I Chiitoitsu

纯属个人训练记录，方便以后复题用
以下均代表个人对题解的理解

Chiitoitsu

题意：（借用自牛客题解）
题解：实因为每种牌数量都是4张，并且初始牌中不会出现超过三张一样的牌，所以我们可以把牌分成两类，一类是已经成队了的，另一类是单牌，显然已经成队的不会再进行替换，可以当作没有，而单牌因为我知道已经打出了哪些牌，所有我每次总可以使得手牌中的单牌都是之前还没有出现过的单牌，即牌堆中还有$3$张一样的，这样我们可以预处理一下，用$dp[i][j]$表示手上还有$i$张单排，牌堆还有$j$张牌时还需要摸牌次数的期望值，那么我根据当前摸的牌是否可以和我手上的单牌配对可分为两种：
1.可以和当前手上单牌配对，那么配对后需要再扔掉一张单牌，当前单牌数减少二（一张被配对了，一张被扔掉了），牌堆内牌数减一,概率为$\frac{3?i}{j}$。
2.不可以和当前手上单牌配对，那么我必定扔掉(因为手上原本的单牌一定有三张还没出现的在牌堆，他们遇到能匹配的概率一定是等于或优于当前摸到的单牌)，那么当前单牌数不变，牌堆内牌数减一,概率为$\frac{j?3?i}{j}$。

状态转移方程为：$dp[i][j]=1+\frac{3?i}{j}?dp[i?2][j?1]+\frac{j?3?i}{j}?dp[i][j?1]$,
注意当$i$为1时：$dp[1][j]=1+\frac{3}{j}?0+\frac{j?3}{j}?dp[i][j?1]=1+\frac{j?3}{j}?dp[i][j?1]$
预处理出$dp$数组后，每次输入判断下有多少张单牌即可
细节和不懂可以看代码

ll mi(ll a,ll b){
	ll res=1;
	while(b){
		if(b%2){
			res=res*a%mod;
		}
		a=a*a%mod;
		b/=2;
	}
	return res;
}
map<string,bool>mp;
ll dp[20][200];//已经配对了i副，还有j张没摸时还要摸牌次数的期望
int main(){
/*cout<<setiosflags(ios::fixed)<<setprecision(8)<<ans<<endl;//输出ans（float）格式控制为8位小数（不含整数部分）*/
/*cout<<setprecision(8)<<ans<<endl;//输出ans（float）格式控制为8位小数（含整数部分）*/
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//同步流
	ll sum=34*4-13;
	for(ll i=3;i<=sum;i++){
		dp[1][i]=(1+(((i-3)*mi(i,mod-2)%mod)*dp[1][i-1]%mod))%mod;
	} 
	for(ll i=3;i<=13;i+=2){
		for(ll j=3;j<=sum;j++){
			dp[i][j]=(1+(((i*3)*mi(j,mod-2)%mod)*dp[i-2][j-1]%mod)+(((j-i*3)*mi(j,mod-2)%mod)*dp[i][j-1]%mod))%mod;
		}
	}
	int t;
	cin>>t;
	for(int times=1;times<=t;times++){
		string s;
		cin>>s;
		string ss;
		int num=0;
		mp.clear();
		for(int i=1;i<s.length();i+=2){
			ss="";
			ss+=s[i-1];
			ss+=s[i];
			if(mp.count(ss)){
				num--;
			}
			else{
				mp[ss]=1;
				num++;
			}
		}
		cout<<"Case #"<<times<<": "<<dp[num][sum]<<endl;
	}
	return 0;
}