Niuke 2022 summer training session I chiitoitsu solution

The main idea of the topic

A person plays mahjong by himself （34 It's a card type , Each of these 4 Zhang ）.
Initial pumping 13 card , Then draw one , Ruohu card , End . Otherwise, discard one .
And in this question , The type of Hu card is only 7 A couple , namely 7 For the same card （ Each pair is different ）.
Ensure that the number of cards with the same starting hand does not exceed 2 Zhang .

Given the starting hand , Ask for the expected number of rounds of Hu cards .
Topic link

Ideas

It's not hard to find out , We just discard the single card , No matter which one is discarded , It has no effect on the results . So our strategy is ： As long as the drawn card cannot be matched with the card in the hand , Then discard this drawn card .

If we still need three pairs of cards, we can play cards （ namely 6 A single card ）, Then our task is Draw any three of the six cards from the stack . Then smoke once , The probability of drawing and not drawing is :
$$\frac{6\ast 3}{remain},\frac{remain-6\ast 3}{remain}$$
remain Represents the number of cards left in the Library , And each of the six card types has three .

We use expectation dp Methods , Write the equation of state transition , set up $f_{i,j}$ It means that we have $i$ A single card , There are still... Left in the library at this time $j$ card . So suppose we draw a matching card , Then the single card in hand will be subtracted 2( Pair one , Discard one ). And whether we draw matching cards or not , The number of libraries will be subtracted 1. So we can write the state transition equation :
$f_{i,j}=1+\frac{3\ast i}{j}\ast f_{i-2,j-1}+\frac{j-3\ast i}{j}\ast f_{i,j-1}$

Note that the problem is to use the inverse of multiplication instead .

Code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const long long mod = 1e9 + 7;

long long qpow(long long a, long long b)
{
    
    long long tmp = 1;
    while(b) {
    
        if(b & 1)
            tmp = tmp * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return tmp;
}

long long div(long long a)
{
    
    return qpow(a, mod - 2);
}

long long sum = 34 * 4 - 13;
long long f[15][34 * 4];

int T;
char ch[31];
string s[20];

int main()
{
    
    for(int j = 3; j <= sum; ++j) {
    
        for(int i = 1; i <= 13; ++i) {
    
            if(j < i * 3)
                continue;
            long long now = 3 * i * div(j) % mod;
            if(i == 1)
                f[i][j] = (1 + (f[i][j - 1] * (1LL + mod - now))) % mod;
            else    
                f[i][j] = (1 + (f[i][j - 1] * (1LL + mod - now) % mod) + f[i - 2][j - 1] * now % mod) % mod;
        }
    }
    scanf("%d", &T);
    for (int test = 1; test <= T; ++test) {
    
        scanf("%s", ch);
        for (int i = 0; i < 13; ++i) s[i] = ch[i * 2], s[i] += ch[i * 2 + 1];
        sort(s, s + 13);
        int duitsu = 0, single = 0;
        for (int i = 0; i < 12; ++i) duitsu += (s[i] == s[i + 1]);
        single = 13 - duitsu * 2;
        printf("Case #%d: %lld\n", test, f[single][sum]);
    }
    return 0;
}