麻将真好(du)van(liu)

  • 首先考虑对于一个状态来说: 摆牌的顺序是没有关系的, 只与牌数有关.

那么如何确定当前局面能否胡牌?

  1. 7个对子胡牌的情况非常好判断.

  2. 考虑顺子胡牌的情况:

dp_{[0/1][i][j][k]}表示当前枚举到第i个花色, 是否已经凑出一个对子, 且第i-2个花色需要j个顺子, 第i-1个花色需要k个顺子–所能够凑出的最大面子数.

如何转移? 枚举当前需多少个从i开始的顺子, 然后i剩下的牌贪心凑刻子即可.

那么dp完之后只要判断\exist j,k \ \ \text{s.t. } dp[1][n][j][k] \ge 4 即可胡牌.

进一步的考虑, 发现花色是不需要考虑的东西, 我们只关心当前dp的数值与牌数量

也就是关心当前状态与转移边

那么可以构成一个”dp自动机”, 即一个模拟所有dp转移的自动机!

爆搜发现状态数不超过4000.

利用自动机可以唯一对应一种摸牌状态.

  • 一个较为经典的期望公式:

\sum_a P[\chi = a]\cdot a = \sum_a{P[x\ge a]}

根据这个式子, 只要求出走了a步没有胡牌的方案数即可.

可以考虑dp: 设f_{i,j,k}表示考虑到no.i个花色, 当前有j张牌, 对应自动机状态为k的方案数.

然后瞎jb搞就好了.

总结

dp可能不是重点吧…

关键在于, 发现题目最关心的仅仅和当前状态(即dp值)与转移决策有关

进而求出dp转移图, 再dp初始状态\to终状态的方案数即可.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1e2 + 5;
const int S = 4e3 + 5;
const int mod = 998244353;

int ans, n, x, a[N], nex[S][5];

namespace {
# define pi pair<mat, mat>
# define fi first
# define se second

    inline void add(int &a, int b) { a += b; if(a >= mod) a -= mod; }
    inline void sub(int &a, int b) { a -= b; if(a < 0) a += mod; }
    inline int mul(int a, int b) { return (LL) a * b % mod; }
    inline void Max(int &a, int b) { if(b > a) a = b; }
    inline void Min(int &a, int b) { if(b < a) a = b; }

    struct mat {
        int dp[3][3];

        bool operator < (const mat &a) const {
            for(int i = 0; i < 3; ++i)
                for(int j = 0; j < 3; ++j)
                    if(dp[i][j] != a.dp[i][j])
                        return dp[i][j] < a.dp[i][j];
            return 0;
        }

        bool operator == (const mat &a) const {
            for(int i = 0; i < 3; ++i)
                for(int j = 0; j < 3; ++j)
                    if(dp[i][j] != a.dp[i][j])
                        return 0;
            return 1;
        }

        mat() {}
        //void clear() { memset(dp, 0, sizeof dp); }
        void set() { memset(dp, -1, sizeof dp); }
        mat trans(int c) {
            static mat res;
            res.set();
            for(int i = 0; i < 3; ++i)
                for(int j = 0; j < 3; ++j) {
                    if(i + j > c || dp[i][j] == -1) continue;
                    for(int k = 0; k <= c - (i + j) && k < 3; ++k)
                        Max(res.dp[j][k], i + (c - (i + j + k)) / 3 + dp[i][j]);
                }
            for(int i = 0; i < 3; ++i)
                for(int j = 0; j < 3; ++j)
                    Min(res.dp[i][j], 4);
            return res;
        }
        inline void chmx(mat a) {
            for(int i = 0; i < 3; ++i)
                for(int j = 0; j < 3; ++j)
                    Max(dp[i][j], a.dp[i][j]);
        }
    };
}

namespace pre {
    int tot, win[S];
    struct o {
        pi g;
        int cnt;

        bool operator < (const o &a) const {
            if(g != a.g) return g < a.g;
            if(cnt != a.cnt) return cnt < a.cnt;
            return 0;
        }

        o() {}
        inline void set() {
            g.fi.set();
            g.se.set();
            cnt = 0;
            g.fi.dp[0][0] = 0;
        }
        inline bool judge() {
            if(cnt == 7) return 1;
            for(int i = 0; i < 3; ++i)
                for(int j = 0; j < 3; ++j)
                    if(g.se.dp[i][j] == 4) return 1;
            return 0;
        }
        o trans(int c) {
            static o res; res = *this;
            if(c >= 2) {
                ++res.cnt;
                Min(res.cnt, 7);
            }
            res.g.fi = res.g.fi.trans(c);
            res.g.se = res.g.se.trans(c);
            if(c >= 2)
                res.g.se.chmx(g.fi.trans(c - 2));
            return res;
        }
    } sta, id[S];
    map<o, int> Hash;

    int dfs(o now) {
        if(Hash.count(now)) return Hash[now];
        int u = ++tot;
        Hash[now] = u;
        id[u] = now;
        win[u] = now.judge();
        if(win[u]) return u;
        for(int c = 0; c <= 4; ++c)
            nex[u][c] = dfs(now.trans(c));
        return u;
    }

    void main() {
        sta.set();
        dfs(sta);
        cout << tot << '\n';
    }
}
using pre :: tot;

namespace sol {
    int f[2][4 * N][S], fac[4 * N], inv[4 * N];

    inline int Pow(int a, int b = mod - 2) {
        int res = 1;
        for(; b; b >>= 1, a = mul(a, a))
            if(b & 1) res = mul(res, a);
        return res;
    }
    inline int C(int n, int m) {
        if(n < 0 || m < 0 || n < m) return 0;
        return mul(fac[n], mul(inv[m], inv[n - m]));
    }
    void init(int n) {
        fac[0] = inv[0] = 1;
        for(int i = 1; i <= n; ++i)
            fac[i] = mul(fac[i - 1], i);
        inv[n] = Pow(fac[n]);
        for(int i = n - 1; i; --i)
            inv[i] = mul(inv[i + 1], i + 1);
    }
    void main() {
        init(4 * n);
        int s = 0;
        f[s][0][1] = 1;
        for(int i = 0; i < n; ++i, s ^= 1) {
            memset(f[s ^ 1], 0, sizeof f[s ^ 1]);
            for(int j = 0; j <= 4 * n; ++j)
                for(int k = 1; k <= tot; ++k) {
                    if(!f[s][j][k]) continue;
                    for(int c = a[i + 1]; c <= 4; ++c) 
                        add(f[s ^ 1][j + c][nex[k][c]], mul(C(4 - a[i + 1], c - a[i + 1]), f[s][j][k]));
                }
        }
      for(int i = 13; i <= 4 * n; ++i)
            for(int j = 1; j <= tot; ++j) {
                if(pre :: win[j] || !f[s][i][j]) continue;
                int mt = mul(fac[4 * n - i], fac[i - 13]);
                add(ans, mul(mt, f[s][i][j]));
            }
        printf("%d\n", mul(ans, inv[4 * n - 13]));
    }
}

int main() {
    pre :: main();
    scanf("%d", &n);
    for(int i = 1; i <= 13; ++i) {
        scanf("%d%*d", &x);
        ++a[x];
    }
    sol :: main();
    return 0;
}