Luogu

LOJ

分析

首先我们并不需要整副牌，我们只需要每种牌的出现次数，也就是说只需要一个长度为 $n$ 的串。

考虑怎么判一副牌能不能和。可以去做一下这道题。

具体实现

设 $f_{i, j, k, 0/1}$ 表示前 $i$ 种牌，$(i-1,i,i+1)$ 要用 $j$ 次，$(i,i+1,i+2)$ 要用 $k$ 次，没有/有雀头的最多面子数。转移比较简单。

我们把第一维去掉，强制 $f$ 值不超过 $4$ 、雀头数不超过 $7$ ，这样子就会有大量重复状态。爆搜可以搜出本质不同的状态只有 $2091$ 种。

那么我们把所有状态预处理出来，然后预处理出对于每个状态追加 $x\in[0,4]$ 张牌的状态，这样子就构成了一个自动机。我们可以把它叫做麻将自动机。

那么我们只要把串丢到麻将自动机上匹配，然后通过末状态即可判断这个串是否能和。

我们要计算的是摸了恰好 $i$ 张后和的概率，可以求个前缀和变为求摸了 $i$ 张后还没和的概率。

考虑 DP。设 $f_{i, j, k}$ 表示前 $i$ 种牌，在麻将自动机的 $j$ 节点，前面已经开了 $k$ 张牌仍未和的概率。

转移直接枚举新加进来几张 $i$ 就行了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#define re register
using namespace std;

inline void chkmax(int& x,int y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400+10;
const int mod=998244353;

inline void add(int& x,int y) { x=(x+y)%mod; }

int tot=0;

struct node {
    int f[3][3][2],cnt;
    inline void init() { memset(f,-1,sizeof(f)),f[0][0][0]=cnt=0; }
    inline int win() {
        if (cnt>=7) return 1;
        for (re int i=0;i<3;++i)
            for (re int j=0;j<3;++j)
                if (f[i][j][1]>=4) return 1;
        return 0;
    }
} rt,S[2100];

bool operator <(node a,node b) {
    if (a.cnt!=b.cnt) return a.cnt<b.cnt;
    for (re int i=0;i<3;++i)
        for (re int j=0;j<3;++j)
            for (re int k=0;k<2;++k)
            if (a.f[i][j][k]!=b.f[i][j][k])
                return a.f[i][j][k]<b.f[i][j][k];
    return 0;
}

inline node transform(node u,int w) {
    node v; v.init(),v.cnt=min(u.cnt+(w>=2),7);
    for (re int i=0;i<3;++i)
        for (re int j=0;j<3;++j) {
            if (~u.f[i][j][0]) {
                for (re int k=0;k<3&&i+j+k<=w;++k)
                    chkmax(v.f[j][k][0],min(u.f[i][j][0]+i+(w-i-j-k>=3),4));
                if (w>=2)
                    for (re int k=0;k<3&&i+j+k<=w-2;++k)
                        chkmax(v.f[j][k][1],min(u.f[i][j][0]+i,4));
            }
            if (~u.f[i][j][1]) {
                for (re int k=0;k<3&&i+j+k<=w;++k)
                    chkmax(v.f[j][k][1],min(u.f[i][j][1]+i+(w-i-j-k>=3),4));
            }
        }
    return v;
}

map<node,int> M;

inline void build(node u) {
    if (u.win()) return;
    if (M.find(u)!=M.end()) return;
    M[u]=++tot,S[tot]=u;
    for (re int i=0;i<=4;++i) build(transform(u,i));
}

int fac[N],ifac[N],inv[N];
int s[N],tr[2100][5];
int f[2][2100][N];

inline int C(int n,int m) {
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int main() {
    rt.init(); build(rt);
    fac[0]=ifac[0]=inv[0]=inv[1]=1;
    for (re int i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%mod;
    for (re int i=2;i<N;++i) inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
    for (re int i=1;i<N;++i) ifac[i]=1ll*ifac[i-1]*inv[i]%mod;

    int n=read();
    for (re int i=1;i<=13;++i) ++s[read()],read();

    for (re int i=1;i<=tot;++i)
        for (re int j=0;j<=4;++j)
            tr[i][j]=M[transform(S[i],j)];
    f[0][1][0]=1;
    for (re int i=1,sum=0;i<=n;++i) {
        int now=i&1,pre=now^1; memset(f[now],0,sizeof(f[now]));
        for (re int j=1;j<=tot;++j)
            for (re int k=s[i];k<=4;++k) {
                if (!tr[j][k]) continue;
                int w=1ll*C(4-s[i],k-s[i])*fac[k-s[i]]%mod;
                for (re int l=0;l<=4*n-k;++l) {
                    if (!f[pre][j][l]) continue;
                    add(f[now][tr[j][k]][l+k],1ll*f[pre][j][l]*w%mod*C(k+l-sum-s[i],k-s[i])%mod);
                }
            }
        sum+=s[i];
    }

    int ans=0;
    for (re int i=13,w=1;i<=4*n;++i) {
        int now=0;
        for (re int j=1;j<=tot;++j) add(now,f[n&1][j][i]);
        add(ans,1ll*now*w%mod);
        w=1ll*w*inv[4*n-i]%mod;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改：2021 年 03 月 23 日 07 : 34 PM
© 允许规范转载