[ZJOI2019] 麻将 题解

首先对于已有的一堆牌，我们应该要能确定它能不能胡。

这部分具体的可以参考我的另一篇博客，顺带说一句，[ZJOI2019] 麻将的前置知识居然被拿去 [GXOI/GZOI2019] 出了个宝牌一大堆~~，ZJOI 恐怖如斯~~。

回到这个题目，对于一个已知状态，我们可以设 $f_{i,0/1/2,0/1/2,0/1}$ 表示前 $i$ 张牌，$i-1$ 开始的顺子有 $0/1/2$ 个，$i$ 开始的顺子有 $0/1/2$ 个，有无雀头的最大面子数。

但是现在状态是未知的，所以考虑 DP of DP，即把这个 $f$ 压到状态里面去。为了方便，我们把 $f_{0/1/2,0/1/2,0/1}$ （注意到这里已经忽略了 $i$，因为 $i$ 对转移没有影响）建一个自动机。而自动机上面的信息就是形如 $f_{0,0,0}=x,f_{0,0,1}=y...$ 这样的多元组，因为还有七对子的特殊牌型，所以在自动机上面额外记录一个 $cnt$ 表示对子数。

乍一看，一共有 $3\times 3\times 2=18$ 个 $f$ 状态，而 $f$ 的取值有 $0/1/2/3/4$ 五种（大于 $4$ 已经没有意义，故可以限制最大值为 $4$），并且还有一个额外的 $cnt$ 需要记录，自动机上的节点数会达到 $5^{18}\times 8=3.0517578125×10^{13}$，我们难以承受。但是显然有很多状态不会被涉及到，比如说 $f_{0,0,0}=3$ 的时候任何 $f$ 值都不会小于 $3$。所以我们可以写一个 BFS 去看看自动机节点数有多少。特别的，如果 $cnt=7$ 或者 $f_{0,0,0}=4$，那么已经胡牌，我们可以建立一个胡牌节点，与此同时，我们也可以把转移边记录下来，特别的，胡牌节点只有自环。代码形如这样。

map <Status, int> mp;
void GetStatus() {
  Status t, nxt; // 这是一个定义状态的结构体
  int cnt = 0;
  q.push(t), mp[t] = ++cnt;
  while (t.cnt != -1) t.Trans(2); // 这里是构造一个胡牌节点
  mp[t] = ++cnt;
  for (RI i = 0; i <= 4; ++i)
    child[mp[t]][i] = mp[t];
  while (!q.empty()) {
    t = q.front(); q.pop();
    for (RI i = 0; i <= 4; ++i) {
      nxt = t, nxt.Trans(i); // 更新 f
      if (mp.find(nxt) == mp.end())
        q.push(nxt), mp[nxt] = ++cnt; // 新建节点
      child[mp[t]][i] = mp[nxt]; // 记录转移边
    }
    if (cnt > 100000) break; // protection
  }
  length = mp.size();
}

至于 $f$ 具体怎么转移大家可以自己推一推。

然后你会发现搜出来只有 1566 个节点（我也不知道为什么和很多博客上写的都不同，我还怀疑了自己好久……），于是我们就可以根据这个来 DP 了（可以把节点看做是内部的 DP）。

设 $g_{i,j,k}$ 表示考虑前 $i$ 种牌，当前牌长度为 $j$，在自动机上面的点 $k$ 的方案数。转移的时候枚举这一种牌有多少张即可，复杂度 $O(n^2\times 1566)$。因为相同种类的牌是有编号区分的，所以转移的时候一定要乘组合数（被卡了好久）。

最后再考虑计算答案。对于一个至少 $k$ 次才能胡牌的状态，它对答案的贡献为 $k$。因为是至少，不好直接求，考虑转化成至多。即改成对于一个至多 $k-1$ 次都不能胡牌的状态，它对答案的贡献为 $k$。而这个状态在 $1\sim k-1$ 次都不能胡牌。所以我们可以把贡献拆分到 $1\sim k-1$ 上面去，每个部分的权值为 $1$。（或者说 $k=\sum_{i=1}^k1$？）。

那么最终答案就是 $\frac{\sum_{i=14}^{4n}\sum_{j=1}^{len}g_{n,i,j}(4n-i)!(i-13)![\text{ $j$ 不是胡牌节点 }]}{(4n-13)!}+1$。代码如下。

#include <bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define RI register int
typedef long long LL;

#define FILEIO(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);

using namespace std;

struct Status { // 自动机中的状态
  int f[3][3][2], cnt;
  Status () {
    for (RI i = 0; i <= 2; ++i)
      for (RI j = 0; j <= 2; ++j)
        for (RI k = 0; k <= 1; ++k)
          f[i][j][k] = -0x3f3f3f3f;
    cnt = f[0][0][0] = 0;
  }
  void Trans(int res) { // 自动机状态的内部转移
    Status nxt;
    int win = 0;
    nxt.cnt = cnt + (res >= 2);
    win |= (nxt.cnt >= 7);
    for (RI i = 0; i <= 2; ++i)
      for (RI j = 0; j <= 2; ++j)
        for (RI k = 0; k <= 1; ++k) {
          for (RI lasi = 0; lasi <= 2; ++lasi)
            for (RI lask = 0; lask <= k; ++lask) {
              int ned = lasi + i + j + 2 * (k - lask);
              if (ned > res) continue;
              nxt.f[i][j][k] = min(4, max(nxt.f[i][j][k], f[lasi][i][lask] + j + (res - ned >= 3)));
            }
        }
    for (RI i = 0; i <= 2; ++i)
      for (RI j = 0; j <= 2; ++j)
        for (RI k = 0; k <= 1; ++k)
          if (nxt.f[i][j][k] < 0)
            nxt.f[i][j][k] = -0x3f3f3f3f;
    win |= (nxt.f[0][0][1] >= 4);
    if (win) // 判胡牌
      for (RI i = 0; i <= 2; ++i)
        for (RI j = 0; j <= 2; ++j)
          for (RI k = 0; k <= 1; ++k)
            nxt.f[i][j][k] = nxt.cnt = -1;
    *this = nxt;
  }
  bool operator < (const Status &A) const {
    if (cnt != A.cnt) return cnt < A.cnt;
    for (RI i = 0; i <= 2; ++i)
      for (RI j = 0; j <= 2; ++j)
        for (RI k = 0; k <= 1; ++k)
          if (f[i][j][k] != A.f[i][j][k])
            return f[i][j][k] < A.f[i][j][k];
    return 0;
  }
};
map <Status, int> mp;
queue <Status> q;
int const MAXN = 2005, mod = 998244353;
int child[MAXN][5];
int f[2][405][MAXN];
int tong[105];
int length;
LL frac[MAXN], invfrac[MAXN];

LL qpow(LL a, LL k) {
  LL re = 1;
  for (; k; k >>= 1, a = a * a % mod)
    if (k & 1) re = re * a % mod;
  return re;
}
void Init(int Max) {
  frac[0] = 1;
  for (RI i = 1; i <= Max; ++i)
    frac[i] = frac[i - 1] * i % mod;
  invfrac[Max] = qpow(frac[Max], mod - 2);
  for (RI i = Max; i >= 1; --i)
    invfrac[i - 1] = invfrac[i] * i % mod;
}

void GetStatus() { // 上文已经解释了
  Status t, nxt;
  int cnt = 0;
  q.push(t), mp[t] = ++cnt;
  while (t.cnt != -1) t.Trans(2);
  mp[t] = ++cnt;
  for (RI i = 0; i <= 4; ++i)
    child[mp[t]][i] = mp[t];
  while (!q.empty()) {
    t = q.front(); q.pop();
    for (RI i = 0; i <= 4; ++i) {
      nxt = t, nxt.Trans(i);
      if (mp.find(nxt) == mp.end())
        q.push(nxt), mp[nxt] = ++cnt;
      child[mp[t]][i] = mp[nxt];
    }
    if (cnt > 100000) break; // protection
  }
  length = mp.size();
}

inline void Add(int &x, int y) { x += y - mod; x += (x >> 31) & mod; }

LL C[10][10];

int main() {
  
#ifdef LOCAL
  FILEIO("a");
#endif

  GetStatus();
  int n; cin >> n;
  C[0][0] = 1;
  C[1][0] = C[1][1] = 1;
  C[2][0] = C[2][2] = 1, C[2][1] = 2;
  C[3][0] = C[3][3] = 1, C[3][1] = C[3][2] = 3;
  C[4][0] = C[4][4] = 1, C[4][1] = C[4][3] = 4, C[4][2] = 6;
  Init(4 * n);
  for (RI i = 1, x, y; i <= 13; ++i)
    cin >> x >> y, ++tong[x];
  int cur = 0, nxt = 1;
  f[nxt][0][1] = 1;
  for (RI i = 1; i <= n; ++i) { // 简单 DP
    swap(cur, nxt);
    memset(f[nxt], 0, sizeof(f[nxt]));
    for (RI j = 0; j <= 4 * (i - 1); ++j)
      for (RI now = 1; now <= length; ++now)
        for (RI k = tong[i]; k <= 4; ++k)
          Add(f[nxt][j + k][child[now][k]], 1ll * f[cur][j][now] * C[4 - tong[i]][k - tong[i]] % mod);
  }
  int ans = 0;
  for (RI i = 14; i <= 4 * n; ++i)
    for (RI j = 1; j <= length; ++j)
      if (j != 2)
        Add(ans, 1ll * f[nxt][i][j] * frac[4 * n - i] % mod * frac[i - 13] % mod);
  ans = (1ll * ans * invfrac[4 * n - 13] % mod + 1) % mod;
  cout << ans << endl;

  return 0;
}

// created by Daniel yuan
/*
     ________
    /        \
   / /      \ \
  / /        \ \
  \            /
   \  ______  /
    \________/
*/

Daniel_yuan's Blog

[ZJOI2019] 麻将题解