暑期牛客多校1： I Chiitoitsu（期望dp，求逆元）

基本题意：

一共136张牌（每个花色四张），初始从牌堆中任给13张牌作为手牌，且每个花色的牌不超过两张，每次摸一张牌，然后从14张牌中弃置一张，弃置的牌不放回牌堆，当手中14张牌两两成对时游戏结束，问结束的期望回合

思路：

预处理dp求期望。因为最终只有7种状态，用dp预处理后，所有询问都是o（1）的复杂度。需要注意的是每次/i时要把i转换成逆元

dp数组：f[剩余卡牌数(<=123)][还差j个对子（<=7）]

状态转移：

代码实现：

#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要在预处理时实现，查询只需要对dp结果查询即可 
			int inv=qmi(i,mod-2,mod);//求逆元 
			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;
}