M_sea

洛谷5279 [ZJOI2019]麻将
LuoguLOJUOJ分析雀魂+自动机+动态规划+九条可怜。首先我们并不需要整副牌,我们只需要每种牌的出现次数,也...
扫描右侧二维码阅读全文
28
2019/05

洛谷5279 [ZJOI2019]麻将

Luogu

LOJ

UOJ

分析

雀魂+自动机+动态规划+九条可怜


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


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

具体实现
设 $f[i][j][k][0/1]$ 表示前 $i$ 种牌,$(i-1,i,i+1)$ 要用 $j$ 次,$(i,i+1,i+2)$ 要用 $k$ 次,没有/有雀头的最多面子数。转移比较简单。


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

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

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


此时我们只要知道 $i$ 张后还没和的概率就可以得到答案了。

那么设 $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;
}
最后修改:2019 年 06 月 09 日 10 : 17 AM

8 条评论

  1. yzhang

    $f[N][2100][N]$不应该是$f[2][2100][N]$吗?不这样空间不会炸吗qwqwq?

    1. smy
      @yzhang

      他用的是神威·太湖之光评测(

      1. M_sea
        @smy

        喵喵喵?

    2. M_sea
      @yzhang

      确实是这样...当初不知道为什么写错了qwq

  2. smy

    woc M_sea又切大火题

    1. M_sea
      @smy

      您不是早就切了吗/kk

  3. xgzc

    woc M_sea又切大火题

    1. M_sea
      @xgzc

      您不是早就会了吗/kk

发表评论