22 Niu Ke Duo School 1 I. Chiitoitsu (Probability dp)

Portal

Approximate meaning of the title: The initial hand has 13 cards, up to two of the same card, a total of 34 kinds of cards, 4 cards of each kind, every time you draw cards from the deck, you are required to make seven pairs,That is to say, if you get seven pairs of the same card, find the number of rounds to reach seven pairs under the optimal strategy

Thinking: Classic probability dp, the optimal strategy is God's perspective, and will not lose the existing single card (that is, assuming that I must touch the existing single row to make a pair)

Considering the state dp[i][j], it means the number of rounds to reach the final state when there are i single cards in hand and j cards in the deck

, dp[i][j] = p1*dp[i-2][j-1] + p2*dp[i][j-1] + 1

p1 means that a card drawn from the deck just forms a pair with a card in the hand, hand-2 deck-1, the probability is 3*i/j

p2 means that a card drawn from the deck does not form a pair with the cards in the hand, and the cards are discarded directly. The hand remains unchanged, the deck is -1, and the probability is (j-3*i)/j

+1 means draw a card

Initialize the final state dp[1][i] = p*dp[1][i-1] + 1, when there is only one card left, that is, when the game is over, draw cards from the deck, if you make a pairThen it ends. If you don't make a pair to continue the deck -1, the probability is (i-3)/i, +1 means to draw a card

Because the answer is modulo, consider the multiplication inverse instead of division, and use fast exponentiation to speed up, the code is as follows:

#include using namespace std;stringstream ss;#define endl "\n"typedef long long ll;typedef pair PII;typedef pair, int> PIII;const int N = 1e5+10, M = 30, mod = 1e9+7;const int INF = 0x3f3f3f3f;int t,T;int n;ll dp[20][200]; // dp[i][j] represents the expectation of reaching the final state when there are i single cards in hand and j cards in the deckll qmi(ll a, ll k){ll res = 1;while(k){if(k & 1) res = res * a % mod;k>>=1;a = a*a % mod;}return res;}void solve(){map mp;string s;cin >> s;int cnt = 0;// Calculate the number of single cards in the initial handfor(int i = 0; i>T;t = T;while(T -- ){solve();}}