Chiitoitsu

题目链接
题意：
打麻将，和普通麻将一样，每一种牌都有四张，开局给13张牌，其中每种牌最多有两张，题中要求求出七对子（也就是每一中牌都有两张）的期望轮数。结果可能是p/q的形式，但题目要求输出的是p*（q的逆元）。
题中还给给出了最优策略：
1：如果摸到的可以组成对子，那么就放入手中的牌，并丢掉一个单牌。
2：如果摸到单牌，直接丢弃。
题解：求期望很容易想到概率dp，我们可以发现在题中，我们讨论的是单牌的数量与剩余牌的数量，所以我们dp的时候要从这两者出发。

设dp[i][j]表示当前有i张单牌，j表示为有剩余j张牌，dp[i][j]表示的是有i张单牌时候的期望轮数。

当剩余牌数当前为i时：
如果当前摸到的牌凑不成，那么我应该转移到dp[i][j-1]表示剩余j-1张牌，还有i张单牌，所以我们现在要求的是转移的概率。当前有i张单牌，所以剩余的牌中还有3张同类型的牌，我能匹配的概率是3 * i / j，不能匹配的概率是 ( j - 3 * i ) / j。
如果当前的牌凑成了，那么我们应该转移到dp[i-2][j-1]，手中牌因为凑成一个对子还要出一张牌，总共减少两张单牌，牌堆中减少一张牌，此时匹配的概率就是(3 * i ) / j
以上就是对转移方程的分析，但是当s==1的时候如果匹配成成功了是不用转移的，直接就赢了，如果没有分析到这一点的话，我们可以从转移方程上分析，dp[1][j]是不可能转移到dp[1-2][j]的。
所以以下就是转移方程：
dp[i][j]=1+( j - 3 ) / j * dp[i][j-1] （i=1）
dp[i][j]=1+( j - 3 * i ) / j * dp[i][j-1]+3 * i / j * dp[i-2][j-1] （i!=1）
方程中＋1的意思是当前正在经历的这一轮。
下面是AC代码：

//
#include
#include
#include
#include
#include
using namespace std;
#define int long long
map<string,int> ma;
const int mod=1e9+7;
int f[20][200];//f[i][j]表示当前状态手中有i张单牌，牌堆中还剩下j张牌
int qmi(int x,int y)//x的y次方
{
    int q=1;
    while(y)
    {
        if(y&1) q=q*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return q;
}
void init()
{
    for(int i=1;i<=13;i++)//枚举单牌的数量
    {
        for(int j=1;j<=123;j++)//枚举牌堆中牌的数量
        {
            if(i==1) f[i][j]=(1+((j-3)*qmi(j,mod-2)%mod*f[i][j-1])%mod)%mod;//这个1的意思是怎样都会经历一轮
            else f[i][j]=(1+((j-3*i)*qmi(j,mod-2)%mod*f[i][j-1])%mod+(3*i*qmi(j,mod-2)%mod*f[i-2][j-1])%mod)%mod;
        }
    }
}
signed main()
{
    init();
    int t;
    cin>>t;
    int flag=0;
    while(t--)
    {
        ma.clear();
        string s;
        cin>>s;
        for(int i=0;i<s.size();i+=2)
        {
            string ss=s.substr(i,2);
            ma[ss]++;
        }
        map<string,int> ::iterator it;
        int cnt=0;
        for(it=ma.begin();it!=ma.end();it++)
        {
            if(it->second==1) cnt++;
        }
        printf("Case #%lld: %lld\n",++flag,f[cnt][123]);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

注：在开始做的时候，不知道为什么总是得不到正确答案，数值总是差的很大，后来才发现是mod错了，在mod的时候一定要严格按照公式去做，否则可能发生错误
(abc)%mod=(a%modb%modc%mod)%mod.