(Niuke multi school I in 2022) i-chiitoitsu (expected DP)

subject ：

  The sample input ：

2
1m9m1p9p1s9s1z2z3z4z5z6z7z
1m1m4m5m1p4m2m2m2p2p2s2s2z

Sample output ：

Case #1: 927105416
Case #2: 100000041

The question ： A pair of mahjong , Altogether 34 Plant designs , There are four in each decor , At first, we choose from all mahjong 13 Mahjong , Enter the one we selected at the beginning 13 There are at most two mahjong for each suit , Next, we randomly choose one of the remaining mahjong and put it into our hand , If the mahjong in our hands at this time is not 7 Yes , Then we choose a mahjong from our hand and discard it to the discard area （ So our hand has always been 13 individual ）, Discarded mahjong is something we can choose at will , Until we have 7 Until a pair of mahjong , Ask how many times we need to draw cards . Be careful , Discarding a card is not putting mahjong into the remaining area , Instead, put it in the discard area , There is also our final state 7 The designs and colors must be different .

analysis ： First, let's take a look at a mahjong, if we don't get together 7 Yes, which mahjong should we discard , Case one , The mahjong we drew just matches a pair of mahjong in our hands , Then we must choose a mahjong that has not been paired in our hands and discard it , This is quite obvious , So what if the mahjong we draw cannot match any mahjong in our hands ？ At this time, we should discard the mahjong we just drew , Why can't we throw away a single card we used to have ？ This is because we need to consider the optimal strategy now , In other words, we are not sure whether the mahjong we currently draw has been discarded before , If it has been discarded before , We keep it now , Then the number of such mahjong in the remaining area must be less than or equal to 2, But if this mahjong we currently draw has not been discarded before , Then it is equivalent for us to discard the currently drawn mahjong and discard a single mahjong in our hand , Because if this mahjong we currently draw has been discarded before , Then the number of such mahjong in the remaining area must be 3, And the mahjong that fell alone in our hand shows that we haven't drawn since , Then the remaining number in the remaining area is also 3, therefore No matter whether the mahjong we currently draw has been discarded before , It must be the best to discard the current mahjong .

set up f[i][j] Indicates that there are already i Yes, and the number of mahjong in the remaining area is j The expected number of times the time distance ends

about （i,j） This situation , In our hand 2*i Mahjong is paired , Yes 13-2*i Mahjong is alone , Because our greedy strategy is to discard the mahjong we draw if it cannot match our mahjong hand , So the number of each kind of mahjong in our hand in the remaining area is 3, Then the number of mahjong we hope to draw next time is （13-2*i）*3, The corresponding probability is （13-2*i）*3/j, Then the corresponding state is transferred f[i+1][j-1], Then the probability that the next mahjong we draw will not match is 1-（13-2*i）*3/j, The state transferred to is f[i][j-1], Then we update the expected array in reverse order to get the answer , Then for each group of input, we only need to process the number of mahjong pairs at the beginning , Because at the beginning, the number of mahjong in the remaining area is 34*4-13.

Here is the code ：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int N=4*34+1-13,mod=1e9+7;
typedef long long ll;
ll f[10][N];//f[i][j] Indicates that there are already i Yes, and the number of remaining mahjong is j The expected number of times the tension distance ends  
char s[10003];
map<string,int>mp;
ll qpow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
int main()
{
	for(int i=6;i>=0;i--)
	for(int j=(13-i*2)*3;j<N;j++)
	{
		ll p=(13-i*2)*3*qpow(j,mod-2)%mod;
		f[i][j]=1+f[i+1][j-1]*p%mod+f[i][j-1]*(1-p);
		f[i][j]=(f[i][j]%mod+mod)%mod;
	}
	int T;
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		mp.clear();
		scanf("%s",s+1);
		int len=strlen(s+1)/2;
		int cnt=0;
		for(int i=1;i<=len;i++)
		{
			string S="";
			S+=s[2*i-1];S+=s[2*i];
			mp[S]++;
			if(mp[S]==2) cnt++;
		}
		printf("Case #%d: %lld\n",_,f[cnt][N-1]);
	}
	return 0;
}