Summer Niuke multi school 1:i chiitoitsu (expectation DP, inverse yuan)

Basic question meaning ：

altogether 136 card （ Four for each Decor ）, Initially, you can give from the deck 13 Cards as hands , And there are no more than two cards in each suit , Touch one card at a time , And then from 14 Discard one of the cards , Discarded cards are not put back on the stack , In the hands of 14 The game ends when cards are paired , Ask the end of the expected round

Ideas ：

Preprocessing dp Expect . Because in the end, only 7 States , use dp After pretreatment , All inquiries are o（1） Complexity . It should be noted that every time /i When you do i Convert to inverse element

dp Array ：f[ Number of cards remaining (<=123)][ Still bad j A couple （<=7）]

State shift ：

Code implementation ：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
const int mod=1e9+7;
const int N=200,M=15;
typedef long long LL;
typedef pair<LL,LL> PII;
string a;
map<string,int> x;
LL f[N][M];

LL qmi(int a,int b,int p){
	LL res=1;
	while(b){
		if(b&1) res=res*a%p;
		a=(LL)a*a%p;
		b>>=1;
	}
	return res;
}

int main(){
	int t;
	cin>>t;
	for(int i=3;i<=123;i++){//dp It should be implemented during preprocessing , The query only needs to be on dp Result query is enough  
			int inv=qmi(i,mod-2,mod);// Inverse element  
			for(int j=1;j<=7&&3*(2*j-1)<=i;j++){
				f[i][j] = 3ll * (2 * j - 1) * inv % mod * (f[i - 1][j - 1] + 1) % mod;
            	f[i][j] = (f[i][j] + 1ll * (i - 3 * (2 * j - 1)) * inv % mod * (f[i - 1][j] + 1) % mod) % mod;
			}
		}
	for(int qa=1;qa<=t;qa++){
		cin>>a;
		int cs=7;
		for(int i=0;i<26;i+=2){
			string y=a.substr(i,2);
			x[y]++;
			//cout<<y<<endl;
			if(x[y]==2) cs--;
		}
		cout<<"Case #"<<qa<<": "<<f[123][cs]%mod<<endl;
		for(int i=0;i<26;i+=2){
			string y=a.substr(i,2);
			x[y]=0;
		}
	}
	return 0;
}