题目链接

LOJ3042

题目描述

现在有一个$4\times n$的一个牌堆并随机打乱。
一开始给定你$13$张牌,问再摸若干张牌,牌集中存在一个可以胡的子集的期望步数。
数据范围:$n\leq 100$

思路要点

先做个解释:顺子是连着的三个,刻子是相同的三个,$\text{面子}=\text{顺子}+\text{刻字}$(我不玩雀魂

子任务讨论

首先需要解决一个子问题就是怎样判断一个牌集拥有一个能够胡的子集。

条件一

第一个条件:四个面子+一个对子
我们参考CodeForces Global Round 1 D的做法,但是这篇博客的代码实现上稍有不同。
一个结论:相同花色顺子最多$2$个,因为三个相同的顺子可以等价给三个不同的刻子,而且对答案没有影响
首先不考虑对子的情况,定义状态$f[i][j][k]$表示当前处理完$[1,i]$花色,其中$(i-1,i)$有$j$对,$i$剩下有$k$个下最大的面子数
注意!我们都是先满足顺子,然后满足刻子
那么考虑加入$i+1$,我们枚举下一个状态还剩下$t$个$i+1$,因为先满足顺子,所以这里假定顺子已经填满了,增加了$i$的贡献,此时还剩下的若干个相同花色的,我们就考虑全部转化成刻子。
所以状态转移方程为:$f[i+1][j][k]=Max\{ i+f[i][j][k]+\lfloor \frac{remain}3\rfloor\}$
但是题目中还需要有一个对子,所以我们把状态定义为$f[0/1][i][j][k]$,其中的$i,j,k$意义不变,新增一维表示是否已经出现对子。$f[0]$和$f[1]$内部的转移还是和上面一样。考虑$f[0]$和$f[1]$之间的转移,如果我们当前加入花色的个数$\geq 2$,我们就可以先消耗两个花色,然后从$f[0]$转移到$f[1]$。

条件二

第二个条件:七个对子
因为状态相对于第一个条件独立,所以直接考虑新开一维$cnt$,表示不同花色的对子个数。
注意!一定是花色不同,即一次修改只能修改$1$

子任务实现

可以开一个结构体,方便处理。(因为我们需要用$\mathrm{map}$去重)

构造自动机

考虑到这个状态的总数应该不会太多,所以我们考虑先预处理出自动机。
稍微科普一下,简单点说,自动机就是状态为节点,转移为有向边的一个东西。
自动机的构造,因为有限状态,所以通过搜索来得到自动机的复杂度是正确的。
构造的时候,我们对于当前状态,必须要枚举下一个牌放多少张$[0,4]$。(这样才能保证我们上面的$DP$的正确性)
这里实测:本质不同的状态数有$3956$,本质不同的不胡状态数有$2092$。
具体构造的方式可以参考下方代码

DP统计方案数

构造了自动机后,我们就要统计方案数了。
定义$f[i][j][k]$表示当前考虑前$i$个花色,摸了$j$张牌,当前的胡牌状态为$k$的方案数。
请注意这里是组合数
考虑第$i+1$张牌摸的数量$t$。
$$f[i+1][j+t][nxtState(k,t)]+=f[i][j][k]\times {all \choose chooseCount}$$

统计答案

如何统计答案,我们先回顾一下原题:

  • 题意:求出存在能胡子集的期望步数。

设$P(i)$为走了$i$就胡了的概率,则答案$Ans=\sum_{i=0}^{\infty} P(i)\times i$
转化$P_1(i)=\sum_{j=i}^{\infty P(i)}$
代入原式得到了$Ans=\sum_{i=1}^{\infty} P_1(i)$
重视一下$P_1(i)$的含义,我们可以发现$P_1(i)$就代表$i$及以后胡的概率,也就是前$i-1$次不胡的概率(因为后面延伸到无限,所以只要满足前$i-1$次不胡,根据题目中所说不难发现$P$的权值就是理论上的最早胡牌巡目数,那么后面一定能胡)
所以题目的答案又被转化成了不能胡的概率和。
我们用式子来表示
$$Ans=\sum \frac {g(i)}{sum(i)}$$
$g(i)$就是手中一共有$i$张牌,还不能胡的方案数。
$sum(i)$表示$i$张牌的总方案数。

时间复杂度是$\mathcal O(3956\times n\times m)$

代码

#include <bits/stdc++.h>

using namespace std;

template <class T> 
void chkmax(T& x, T y) {
  x = x > y ? x : y; 
}

template <class T> 
void chkmin(T& x, T y) {
  x = x < y ? x : y;
}

template <class T> 
void read(T& x) {
  x = 0; char ch = 0; int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
  x *= f;
}

template <class T> 
void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + 48);
}

template <class T> 
void writeln(T x) {
  write(x), puts("");
}

const int SIZE = 4000;

struct State {
  int dp[3][3];
  
  State() {
    memset(dp, -1, sizeof dp);
  }
  
  friend bool operator < (State a, State b) {
    for (int i = 0; i <= 2; i++) {
      for (int j = 0; j <= 2; j++) {
        if (a.dp[i][j] != b.dp[i][j]) {
          return a.dp[i][j] < b.dp[i][j];
        }
      }
    }
    return 0;
  }
  
  friend State operator + (State a, int num) {
    State res;
    for (int i = 0; i <= 2; i++) {
      for (int j = 0; j <= 2; j++) {
        if (~a.dp[i][j]) {
          for (int k = 0; k <= 2 && i + j + k <= num; k++) {
            chkmax(res.dp[j][k], min(4, a.dp[i][j] + i + (num - i - j - k) / 3));
          }
        }
      }
    }
    return res;
  } 
  
  friend State operator + (State a, State b) {
    for (int i = 0; i <= 2; i++) {
      for (int j = 0; j <= 2; j++) {
        chkmax(a.dp[i][j], b.dp[i][j]);
      }
    }
    return a;
  }
};

struct Mahjong {
  pair<State, State> s;
  int cnt;
  
  Mahjong() {
    memset(s.first.dp, -1, sizeof s.first.dp);
    memset(s.second.dp, -1, sizeof s.second.dp);
    s.first.dp[0][0] = cnt = 0;
  }
  
  friend bool operator < (Mahjong a, Mahjong b) {
    return a.cnt == b.cnt ? a.s < b.s : a.cnt < b.cnt;
  }
  
  friend Mahjong operator + (Mahjong a, int num) {
    a.cnt = min(7, a.cnt + (num >= 2));
    a.s.second = a.s.second + num;
    if (num >= 2) {
      a.s.second = a.s.second + (a.s.first + (num - 2));
    }
    a.s.first = a.s.first + num;
    return a;
  }
  
  bool check() {
    if (cnt >= 7) {
      return 1;
    }
    for (int i = 0; i <= 2; i++) {
      for (int j = 0; j <= 2; j++) {
        if (s.second.dp[i][j] >= 4) {
          return 1;
        }
      }
    }
    return 0;
  }
};

map<Mahjong, int> idx;
int tot;
bool finish[SIZE];
Mahjong g[SIZE];

void dfs(Mahjong sta) {
  if (idx.count(sta)) {
    return;
  }
  idx[sta] = ++tot;
  finish[tot] = sta.check();
  g[tot] = sta;
  for (int i = 0; i <= 4; i++) {
    dfs(sta + i);
  }
}

const int MOD = 998244353;
const int N = 105;

int n;
int a[N];
int binom[5][5];
int trans[SIZE][5];
int dp[N][N << 2][4000];

int mul(int x, int y) {
  return (long long)x * y % MOD;
}

int add(int x, int y) {
  return (x += y) >= MOD ? x -= MOD : x;
}

int power(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, x = mul(x, x)) {
    if (y & 1) {
      res = mul(res, x);
    }
  }
  return res;
}

int main() {
  dfs(Mahjong());
  for (int i = 1; i <= tot; i++) {
    for (int j = 0; j <= 4; j++) {
      trans[i][j] = idx[g[i] + j];
    }
  }
  binom[0][0] = 1;
  for (int i = 1; i <= 4; i++) {
    binom[i][0] = binom[i][i] = 1;
    for (int j = 1; j < i; j++) {
      binom[i][j] = add(binom[i - 1][j], binom[i - 1][j - 1]);
    }
  }
  read(n);
  for (int i = 1; i <= 13; i++) {
    int x, y;
    read(x), read(y);
    a[x]++;
  }
  dp[0][0][1] = 1;
  for (int i = 0; i <= n - 1; i++) {
    for (int j = 0; j <= 4 * i; j++) {
      for (int k = 1; k <= tot; k++) {
        for (int t = a[i + 1]; t <= 4; t++) {
          dp[i + 1][j + t][trans[k][t]] = add(dp[i + 1][j + t][trans[k][t]], mul(dp[i][j][k], binom[4 - a[i + 1]][t - a[i + 1]]));
        }
      }
    }
  }
  int ans = 0;
  for (int i = 13; i <= n * 4; i++) {
    int sum = 0, t = 0;
    for (int j = 1; j <= tot; j++) {
      sum = add(sum, dp[n][i][j]);
      if (!finish[j]) {
        t = add(t, dp[n][i][j]);
      }
    }
    ans = add(ans, mul(t, power(sum, MOD - 2)));
  }
  writeln(ans);
  return 0;
}
最后修改:2020 年 02 月 21 日 01 : 23 AM
如果觉得我的文章对你有用,请随意赞赏