fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ull = unsigned long long;
  5. using ld  = long double;
  6.  
  7. static ull Cbinom[53][53];
  8.  
  9. // ranks in order 2..A (Ace last) to make 10-J-Q-K-A consecutive,
  10. // and handle A-2-3-4-5 via wrap check at Ace.
  11. static const string RANKS = "23456789TJQKA";
  12.  
  13. int rIndex(char r) {
  14.     return (int)RANKS.find(r);
  15. }
  16. int sIndex(char s) {
  17.     if (s == 'c') return 0;
  18.     if (s == 'd') return 1;
  19.     if (s == 'h') return 2;
  20.     return 3; // 's'
  21. }
  22.  
  23. struct RunTrans {
  24.     // next_run[run_state][presence_mask], hit if any suit completes length-5 here
  25.     int next_run[625][16];
  26.     bool hit[625][16];
  27.     RunTrans() {
  28.         // decode run_state into 4 base-5 digits
  29.         int dig[625][4];
  30.         for (int st = 0; st < 625; st++) {
  31.             int x = st;
  32.             for (int s = 0; s < 4; s++) {
  33.                 dig[st][s] = x % 5;
  34.                 x /= 5;
  35.             }
  36.         }
  37.         for (int st = 0; st < 625; st++) {
  38.             for (int mask = 0; mask < 16; mask++) {
  39.                 bool found = false;
  40.                 int nd[4];
  41.                 for (int s = 0; s < 4; s++) {
  42.                     bool present = (mask >> s) & 1;
  43.                     int d = dig[st][s];
  44.                     if (present) {
  45.                         if (d == 4) found = true;          // 4 + present => 5 in a row
  46.                         nd[s] = min(4, d + 1);
  47.                     } else {
  48.                         nd[s] = 0;
  49.                     }
  50.                 }
  51.                 int enc = 0, mul = 1;
  52.                 for (int s = 0; s < 4; s++) {
  53.                     enc += nd[s] * mul;
  54.                     mul *= 5;
  55.                 }
  56.                 next_run[st][mask] = enc;
  57.                 hit[st][mask] = found;
  58.             }
  59.         }
  60.     }
  61. };
  62.  
  63. static RunTrans RT;
  64.  
  65. // all subsets of a 4-bit mask, each with its popcount
  66. static vector<pair<int,int>> subOf[16];
  67.  
  68. int main() {
  69.     ios::sync_with_stdio(false);
  70.     cin.tie(nullptr);
  71.  
  72.     // binom
  73.     for (int n = 0; n <= 52; n++) {
  74.         Cbinom[n][0] = Cbinom[n][n] = 1;
  75.         for (int k = 1; k < n; k++) {
  76.             Cbinom[n][k] = Cbinom[n-1][k-1] + Cbinom[n-1][k];
  77.         }
  78.     }
  79.  
  80.     // subsets
  81.     for (int m = 0; m < 16; m++) {
  82.         int sub = m;
  83.         while (true) {
  84.             subOf[m].push_back({sub, __builtin_popcount((unsigned)sub)});
  85.             if (sub == 0) break;
  86.             sub = (sub - 1) & m;
  87.         }
  88.     }
  89.  
  90.     int m;
  91.     cin >> m;
  92.     string h1, h2;
  93.     cin >> h1 >> h2;
  94.     int n;
  95.     cin >> n;
  96.     vector<string> b(n);
  97.     for (int i = 0; i < n; i++) cin >> b[i];
  98.  
  99.     // known_mask[r] = 4-bit suits present among fixed known cards
  100.     int known_mask[13] = {0};
  101.     auto addKnown = [&](const string& c) {
  102.         int r = rIndex(c[0]);
  103.         int s = sIndex(c[1]);
  104.         known_mask[r] |= (1 << s);
  105.     };
  106.  
  107.     addKnown(h1);
  108.     addKnown(h2);
  109.  
  110.     int k = 0;
  111.     for (auto &x : b) {
  112.         if (x == "?") k++;
  113.         else addKnown(x);
  114.     }
  115.  
  116.     int avail_mask[13];
  117.     int R = 0;
  118.     for (int r = 0; r < 13; r++) {
  119.         avail_mask[r] = (~known_mask[r]) & 0b1111;
  120.         R += __builtin_popcount((unsigned)avail_mask[r]);
  121.     }
  122.  
  123.     ull total = Cbinom[R][k];
  124.  
  125.     // decide mode
  126.     enum Mode { FK_ONLY, SF_ONLY, ALL_THREE };
  127.     Mode mode;
  128.     if (m == 1 || m == 3 || m == 5) mode = FK_ONLY;
  129.     else if (m == 4 || m == 6 || m == 7 || m == 8) mode = SF_ONLY;
  130.     else mode = ALL_THREE;
  131.  
  132.     ull favorable = 0;
  133.  
  134.     if (mode == FK_ONLY) {
  135.         // dp0[j]=ways with no four-kind yet, dp1[j]=ways with four-kind already
  136.         vector<ull> dp0(k+1, 0), dp1(k+1, 0);
  137.         dp0[0] = 1;
  138.         for (int r = 0; r < 13; r++) {
  139.             int a = __builtin_popcount((unsigned)avail_mask[r]);
  140.             int kn = __builtin_popcount((unsigned)known_mask[r]);
  141.             vector<ull> ndp0(k+1, 0), ndp1(k+1, 0);
  142.  
  143.             // already true
  144.             for (int j = 0; j <= k; j++) if (dp1[j]) {
  145.                 for (int t = 0; t <= a && j+t <= k; t++) {
  146.                     ndp1[j+t] += dp1[j] * Cbinom[a][t];
  147.                 }
  148.             }
  149.             // not yet
  150.             for (int j = 0; j <= k; j++) if (dp0[j]) {
  151.                 for (int t = 0; t <= a && j+t <= k; t++) {
  152.                     ull ways = Cbinom[a][t];
  153.                     if (kn + t == 4) ndp1[j+t] += dp0[j] * ways;
  154.                     else             ndp0[j+t] += dp0[j] * ways;
  155.                 }
  156.             }
  157.             dp0.swap(ndp0);
  158.             dp1.swap(ndp1);
  159.         }
  160.         favorable = dp1[k];
  161.     }
  162.  
  163.     if (mode == SF_ONLY) {
  164.         const int SS = 625 * 16; // run_state * 16 + wheel_mask
  165.         auto enc = [&](int run, int wheel){ return run*16 + wheel; };
  166.  
  167.         vector<ull> dpFalse((k+1)*SS, 0), dpFalse2((k+1)*SS, 0);
  168.         vector<ull> dpTrue(k+1, 0), dpTrue2(k+1, 0);
  169.  
  170.         dpFalse[0*SS + enc(0, 15)] = 1; // wheel_mask starts as all 1s (possible), AND over ranks 2..5.
  171.  
  172.         for (int r = 0; r < 13; r++) {
  173.             fill(dpFalse2.begin(), dpFalse2.end(), 0);
  174.             fill(dpTrue2.begin(), dpTrue2.end(), 0);
  175.  
  176.             int km = known_mask[r];
  177.             int am = avail_mask[r];
  178.             int a  = __builtin_popcount((unsigned)am);
  179.  
  180.             // true transitions can ignore suit pattern => just choose t cards among a
  181.             for (int j = 0; j <= k; j++) if (dpTrue[j]) {
  182.                 for (int t = 0; t <= a && j+t <= k; t++) {
  183.                     dpTrue2[j+t] += dpTrue[j] * Cbinom[a][t];
  184.                 }
  185.             }
  186.  
  187.             // false transitions enumerate subsets (<=16)
  188.             for (int j = 0; j <= k; j++) {
  189.                 ull *row = &dpFalse[j*SS];
  190.                 for (int st = 0; st < SS; st++) {
  191.                     ull val = row[st];
  192.                     if (!val) continue;
  193.                     int run = st / 16;
  194.                     int wheel = st % 16;
  195.  
  196.                     for (auto [sub, t] : subOf[am]) {
  197.                         if (j + t > k) continue;
  198.                         int presence = km | sub;
  199.  
  200.                         int run2 = RT.next_run[run][presence];
  201.                         bool hit = RT.hit[run][presence];
  202.  
  203.                         int wheel2 = wheel;
  204.                         if (r <= 3) wheel2 = wheel & presence; // ranks 2..5
  205.  
  206.                         // wheel A2345 detected at Ace
  207.                         if (r == 12 && (wheel & presence)) hit = true;
  208.  
  209.                         if (hit) dpTrue2[j+t] += val;
  210.                         else     dpFalse2[(j+t)*SS + enc(run2, wheel2)] += val;
  211.                     }
  212.                 }
  213.             }
  214.  
  215.             dpFalse.swap(dpFalse2);
  216.             dpTrue.swap(dpTrue2);
  217.         }
  218.  
  219.         favorable = dpTrue[k];
  220.     }
  221.  
  222.     if (mode == ALL_THREE) {
  223.         // state: run(0..624), wheel(0..15), pairCnt(0..2), hasTrip(0/1)
  224.         const int SS = 625 * 16 * 3 * 2;
  225.  
  226.         auto enc = [&](int run, int wheel, int pairCnt, int hasTrip) {
  227.             return (((run * 16 + wheel) * 3 + pairCnt) * 2 + hasTrip);
  228.         };
  229.  
  230.         vector<ull> dpFalse((k+1)*SS, 0), dpFalse2((k+1)*SS, 0);
  231.         vector<ull> dpTrue(k+1, 0), dpTrue2(k+1, 0);
  232.  
  233.         dpFalse[0*SS + enc(0, 15, 0, 0)] = 1;
  234.  
  235.         for (int r = 0; r < 13; r++) {
  236.             fill(dpFalse2.begin(), dpFalse2.end(), 0);
  237.             fill(dpTrue2.begin(), dpTrue2.end(), 0);
  238.  
  239.             int km = known_mask[r];
  240.             int am = avail_mask[r];
  241.             int a  = __builtin_popcount((unsigned)am);
  242.             int kn = __builtin_popcount((unsigned)km);
  243.  
  244.             // true: only choose counts matter
  245.             for (int j = 0; j <= k; j++) if (dpTrue[j]) {
  246.                 for (int t = 0; t <= a && j+t <= k; t++) {
  247.                     dpTrue2[j+t] += dpTrue[j] * Cbinom[a][t];
  248.                 }
  249.             }
  250.  
  251.             // false: enumerate subsets for SF tracking
  252.             for (int j = 0; j <= k; j++) {
  253.                 ull *row = &dpFalse[j*SS];
  254.                 for (int st = 0; st < SS; st++) {
  255.                     ull val = row[st];
  256.                     if (!val) continue;
  257.  
  258.                     int tmp = st;
  259.                     int hasTrip = tmp % 2; tmp /= 2;
  260.                     int pairCnt = tmp % 3; tmp /= 3;
  261.                     int wheel   = tmp % 16;
  262.                     int run     = tmp / 16;
  263.  
  264.                     for (auto [sub, t] : subOf[am]) {
  265.                         if (j + t > k) continue;
  266.                         int presence = km | sub;
  267.  
  268.                         int run2 = RT.next_run[run][presence];
  269.                         bool win = RT.hit[run][presence];
  270.  
  271.                         int wheel2 = wheel;
  272.                         if (r <= 3) wheel2 = wheel & presence;
  273.  
  274.                         // wheel A2345 at Ace
  275.                         if (r == 12 && (wheel & presence)) win = true;
  276.  
  277.                         int c = kn + t;          // total cards of this rank in final set
  278.                         if (c == 4) win = true;  // four of a kind
  279.  
  280.                         int pairCnt2 = pairCnt + (c >= 2 ? 1 : 0);
  281.                         if (pairCnt2 > 2) pairCnt2 = 2;
  282.                         int hasTrip2 = hasTrip || (c >= 3);
  283.  
  284.                         if (hasTrip2 && pairCnt2 == 2) win = true; // full house
  285.  
  286.                         if (win) dpTrue2[j+t] += val;
  287.                         else     dpFalse2[(j+t)*SS + enc(run2, wheel2, pairCnt2, hasTrip2)] += val;
  288.                     }
  289.                 }
  290.             }
  291.  
  292.             dpFalse.swap(dpFalse2);
  293.             dpTrue.swap(dpTrue2);
  294.         }
  295.  
  296.         favorable = dpTrue[k];
  297.     }
  298.  
  299.     ld ans = (total == 0 ? 0.0L : (ld)favorable / (ld)total);
  300.     cout << fixed << setprecision(15) << (double)ans << "\n";
  301.     return 0;
  302. }
  303.  
Success #stdin #stdout 0.01s 6056KB
comments (?)
stdin
copy 
9
7d 8d
11
5d ? Qc 2d Kh Ad ? 8c 9c 8s 6d
stdout
copy 
0.898780487804878
https://ideone.com/SrDTfa
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!