【洛谷5279】[ZJOI2019] 麻将（“胡牌自动机”上DP）

点此看题面

大致题意： 给你13张麻将牌，问你期望再摸多少张牌可以满足存在一个胡的子集。

似乎ZJOI2019Day1的最大收获是知道了什么是胡牌？

一个显然的性质

首先我们要知道一个显然的性质，即对于一副牌，我们仅需要考虑其每张牌的张数，而顺序是没有任何关系的。

因此，对于一副牌，我们可以将其转化为一个长度为\(n\)，每个位置上为\(0\sim4\)的序列。

这样就方便操作了许多。

胡牌自动机

在前面性质的基础上，我们来考虑如何判断一副牌，即一个长度为\(n\)的序列是否能胡。

我们似乎可以建一个自动机（可以以其作用命名为胡牌自动机）去处理它。

建自动机的前奏：\(DP\)

那么我们该如何去建这个自动机呢？

考虑如果我们能得出一个判断一副牌是否能胡的\(DP\)，然后把每个状态看作自动机的点，\(DP\)转移看作自动机的边，则一个自动机就建成了。

于是问题又变成了：如何用\(DP\)来判断一副牌是否能胡。

设\(f_{0/1,i,j,k}\)表示处理完前\(i\)种牌，还剩\(j\)组\((i-1,i)\)以及\(k\)张\(i\)，且存在（\(1\)）/不存在（\(0\)）对子时最多的面子数。

由于\(j\ge3\)时，我们可以用\(3\)个\(i-1\)和\(3\)个\(i\)各自组成面子；\(k\ge3\)时，我们可以直接用\(3\)个\(i\)组成面子。

因此，\(0\le j,k\le2\)。

所以可以考虑建一个\(3*3\)的矩阵存下\(f_{0/1,i}\)的全部答案。

假设加入了\(x\)张牌，则我们进行如下几种转移：

将\(f_{0,i}\)从\(f_{0,i-1}\)加\(x\)张牌转移过来。
将\(f_{1,i}\)从\(f_{1,i-1}\)加\(x\)张牌转移过来。
如果\(x>1\)，则将\(f_{1,i}\)从\(f_{0,i-1}\)加\(x-2\)张牌转移过来。

转移过程中，我们枚举若干张牌和之前的\((i-2,i-1)\)拼面子，保留若干组\((i-1,i)\)和若干张\(i\)，然后拿剩下的牌尽可能地拼面子，这样即可进行转移。

根据定义，若\(f_{1,i}>3\)，则这副牌就能胡了。

说到这里，或许你会发现，我们在这个\(DP\)中并没有考虑七对子的情况，这在后面会特判处理。

正式开始建自动机

接下来我们考虑如何将这个\(DP\)转化为自动机。

首先，我们确定一个初始状态（一张牌都没有）。

然后，以类似于\(BFS\)的方式，找到未处理过的节点，枚举新加入的牌数，然后通过\(DP\)转移的方式得出子节点的状态。

不难发现，前面的\(i\)在这里没有任何作用，可以不用记录。因为我们是从每个节点一步步转移的。

而\(0/1\)这个状态还是十分必要的，因此我们可以考虑，对自动机上每个节点开两个矩阵\(P_{0/1}\)，来进行转移。

此外，由于前面提到过的七对子，我们再开一个变量\(t\)记录出现的对子个数。

则综上所述，一个节点是胡的，当且仅当其\(P_1\)中存在一个元素大于\(3\)或\(t\ge7\)。

而为了提高效率，我们可以把所有胡的节点全部压成一个节点，以其\(t=-1\)作为特殊标记即可。

对于其他节点，我们可以开个\(map\)判断一种节点是否已经出现过（注意要将\(t,P_{0/1}\)全部进行比较），出现过则直接连边，否则先新建节点然后再连边。

顺便提一句，这里的\(BFS\)只要按节点编号从小到大枚举即可，无须队列。

显然按此方式建出来的胡牌自动机形态是固定的，即对于任何数据长得都一样。

具体实现详见代码。

胡牌自动机上\(DP\)

现在，我们到了这道题的最后一个关键步骤，胡牌自动机上\(DP\)。

我们可以设\(g_i\)表示摸了\(i\)张牌后不胡的方案数，则答案就为：

\[\frac{\sum_{i=1}^{4n-13}g_ii!(4n-13-i)!}{(4n-13)!}+1
\]

其中分子中的\(i!\)和\((4n-13-i)!\)表示这\(i\)张牌和剩下的\(4n-13-i\)张牌放的顺序任意，可以随便放；分母中的\((4n-13)!\)是总方案数，显然算期望必须要除；加\(1\)是因为我们选择\(i\)张牌后依然不能胡，需要\(+1\)。

然后考虑如何\(DP\)。

设\(f_{i,j,k}\)表示处理到第\(i\)张牌，共摸了\(j\)张牌，走到了胡牌自动机上的\(k\)号节点的方案数。

那么显然我们可以枚举一个摸的牌数\(t\)（\(0≤t≤4-a_i\)，其中\(a_i\)为初始\(13\)张牌中\(i\)的张数），然后从\(f_{i,j,k}\)向\(f_{i+1,j+t,O_k.Son_{a_i+t}}\)转移，其中\(O_k.Son_{a_i+t}\)表示胡牌自动机上\(k\)号节点的第\(a_i+t\)个儿子。

还有\(4-a_i\)张牌中选\(t\)张牌的方案数\(C_{4-a_i}^t\)要记得乘上。

这个\(DP\)转移应该是比较显然，也比较简单的。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 100

#define M 400

#define X 998244353

#define Gmax(x,y) (x<(y)&&(x=(y)))

#define Inc(x,y) ((x+=(y))>=X&&(x-=X))

#define Qinv(x) Qpow(x,X-2)

using namespace std;

int n,m,a[N+5],Fac[M+5],Inv[M+5];

I int Qpow(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}

class HuAutomation//胡牌自动机

{

    private:

        #define SZ 2092//实测自动机大小

        #define C(x,y) (1LL*Fac[x]*Inv[y]%X*Inv[(x)-(y)]%X)//组合数

        #define Pos(x) (p.count(x)?p[x]:(O[p[x]=++tot]=x,tot))//求节点编号，若不存在则新建一个

        #define Extend(x) for(j=0;j^5;++j) O[x].S[j]=Pos(O[x]+j);//扩展

        class Mat//矩阵

        {

            private:

                #define CM Con Mat&

                #define Rp for(RI i=0,j;i^3;++i) for(j=0;j^3;++j)

                #define S (i+j+k)

                int f[3][3];

            public:

                I Mat() {Rp f[i][j]=-1;}I int* operator [] (CI x) {return f[x];}

                I bool operator != (Mat o) Con {Rp if(f[i][j]^o[i][j]) return 1;return 0;}//不等于

                I bool operator < (Mat o) Con {Rp if(f[i][j]^o[i][j]) return f[i][j]<o[i][j];}//比大小，用于map

                I bool Check() Con {Rp if(f[i][j]>3) return 1;return 0;}//判断是否能胡

                I void F5(Mat o,CI t)//更新

                {

                    Rp if(~o[i][j]) for(RI k=0;k^3&&S<=t;++k)//i,j,k分别枚举用于拼面子、用于保留(i-1,i)、用于保留i和直接拼面子的牌数

                        Gmax(f[j][k],min(i+o[i][j]+(t-S)/3,4));//转移更新信息（要向4取min是因为大于4没有意义，同时提高效率）

                }

                #undef S

        };

        struct node//存储一个节点的信息

        {

            int t,S[5];Mat P[2];I node() {t=S[0]=S[1]=S[2]=S[3]=S[4]=0,P[0]=P[1]=Mat();}

            I bool operator < (Con node& o) Con//用于map

            {

                return t^o.t?t<o.t:(P[0]!=o.P[0]?P[0]<o.P[0]:(P[1]!=o.P[1]?P[1]<o.P[1]:0));

            }

            I node operator + (CI x) Con//加上x张新牌

            {

                if(IsHu()) return Hu();node res;//如果已经胡了直接返回

                res.P[0].F5(P[0],x),res.P[1].F5(P[1],x),x>1&&(res.P[1].F5(P[0],x-2),0),//进行转移

                res.t=t+(x>1),res.IsHu()&&(res=Hu(),0);return res;//统计对子数，然后判断是否胡

            }

            I bool IsHu() Con {return !~t||t>=7||P[1].Check();}//已经胡或者七对子或者存在4个面子和1个对子

            I node Hu() Con {node x;return x.t=-1,x;}//胡牌的特殊标记

        }O[SZ+5];map<node,int> p;

        I node Begin() {node x;return x.P[0][0][0]=0,x;}//初始状态

        I node Hu() {node x;return x.t=-1,x;}//胡牌的特殊标记

    public:

        int tot,f[N+5][M+5][SZ+5];

        I void Build()//建自动机

        {

            RI i,j;p[O[1]=Begin()]=1,p[O[2]=Hu()]=tot=2;//建立初始状态和胡牌状态

            Extend(1);for(i=3;i<=tot;++i) Extend(i);//对除第2个（胡牌）以外的其他状态进行扩展

        }

        I void DP()//DP求解答案

        {

            for(RI i=f[0][0][1]=1,j,k,t;i<=n;++i) for(j=m;~j;--j)//枚举当前是第i张牌，共摸了j张牌

                for(k=1;k<=tot;++k) if(f[i-1][j][k]) for(t=0;t<=4-a[i];++t)//枚举在胡牌自动机哪个节点上，以及现在摸的牌数

                    Inc(f[i][j+t][O[k].S[a[i]+t]],1LL*f[i-1][j][k]*C(4-a[i],t)%X);//转移，注意乘上组合数系数

        }

}H;

I void CInit(CI x)//初始化

{

    RI i;for(Fac[0]=i=1;i<=x;++i) Fac[i]=1LL*Fac[i-1]*i%X;//初始化阶乘

    for(Inv[x]=Qinv(Fac[x]),i=x-1;~i;--i) Inv[i]=1LL*Inv[i+1]*(i+1)%X;//初始化阶乘逆元

}

#define Calc(x,y) Inc(ans,1LL*H.f[n][x][y]*Fac[i]%X*Fac[m-i]%X)//统计答案

int main()

{

    RI i,j,x,y,ans=0;for(H.Build(),scanf("%d",&n),i=1;i<=13;++i) scanf("%d%d",&x,&y),++a[x];//读入数据+预处理

    for(m=(n<<2)-13,CInit(m),H.DP(),i=1;i<=m;++i) for(Calc(i,1),j=3;j<=H.tot;++j) Calc(i,j);//统计答案，注意跳过2号节点

    return printf("%lld",1LL*ans*Inv[m]%X+1),0;//输出答案，除以总状态数然后加1

}

巴特西