"Weilai Cup" 2022 Niuke summer multi school training camp 1 I chiitoitsu (probability DP)

" Weilai cup "2022 Niuke summer multi school training camp 1 I Chiitoitsu( probability dp)

The question ： The beginning is for you $13$ card , At most two cards of the same card . Add what you have $13$ The total number of cards is $136$ Zhang , That is, there are $34$ Types , Each type of card has $4$ Zhang . Make up $7$ What are the expectations for different types of cards

Ideas ： First of all, the given string for each test is Unique , And the same number of cards is up to two . So obviously, as long as the number of cards to start is $2$ The cards appear the same number of times , No matter what brand , Then the final expectation is the same . We are thinking about using probability dp To solve this problem . hypothesis $dp[i][j]$ ,$i$ It refers to the number of cards on hand $2$ The number of cards , $j$ It refers to how many cards can be selected on the desktop , That is, the initial number of cards that can be selected is $136-13=123$ , Then assume that the number of cards in the string is $2$ The number of cards is $i$, Then our ultimate expectation is $dp[i][123]$ . So what we need to do is pretreatment $dp$ Array . Is the total $O(7\ast 123)$ Complexity , Then count the number of cards played each time $2$ The number of cards , then $O(1)$ Query can be . Next we deduce dp Transfer equation The best strategy is to have a single hand , We will play single row , Then get a card and form a pair with another card in your hand . namely $dp[i][j]+=dp[i+1][j-1]$$\ast$$(The\; probability\; of\; getting\; a\; pair)$, Another situation is that you take a card from the table but can't form a pair , Play this card, that is $dp[i][j]+=dp[i][j-1]$$\ast$$(The\; probability\; of\; not\; getting\; a\; pair)$. So the transfer equation is $dp[i][j]=d[i+1][j-1]$$\ast$$(The\; probability\; of\; getting\; a\; pair)$ +$dp[i][j-1]$$\ast$$(The\; probability\; of\; not\; getting\; a\; pair)$.

Code ：

/* * @author: Snow * @LastEditTime: 2022-07-19 16:39:26 * @Description: Algorithm Contest */
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long 
#pragma GCC optimize(3)
typedef pair<int,int>PII;
#define pb emplace_back
int dp[10][150];
const int mod = 1e9+7;
map<string,int>mp;
int qmi(int a,int b){
    
    int res=1;
    while(b){
    
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void init(){
    
    for(int i=6;i>=0;i--){
    
        int good=(13-i*2)*3;
        for(int j=good;j<=123;j++){
    
            int bad=j-good;
            int fact=qmi(j,mod-2);
            dp[i][j]=(dp[i+1][j-1]*good%mod*fact%mod+dp[i][j-1]*bad%mod*fact%mod+1)%mod;
        }
    }
}
signed main(){
    
    init();
    int T;
    cin>>T;
    for(int _=1;_<=T;_++){
    
        string s;
        cin>>s;
        mp.clear();
        int sum=0;
        string ss;
        for(int i=0;i<s.size();i+=2){
    
            ss="";
            ss+=s[i];
            ss+=s[i+1];
            mp[ss]++;if(mp[ss]>1)sum++;
        }
        printf("Case #%lld: %lld\n",_,dp[sum][123]);
    }
    return 0;
}