[ZJOI2019]麻将 题解（dp 套 dp）

前言

做这道题的想法从看到这场比赛的 T2 的题解时就开始了。3.1 ~ 3.16 号，共 16 天的历程，我才终于搞出来这道题。在这 16 天里，我每天都要花一点时间在这题上。我做题的周期有点太长了吧。。。感谢 lzy 巨佬为 idea 与调试作出的贡献。

题面

有一副奇怪的麻将，每张牌的面值是 $1$1 ~ $n$n 中的一个整数，每种面值的牌都有恰好四张，分别按 $1$1 ~ $4$4 标号。

定义：

对子：两张面值一样的牌。

刻子：三张面值一样的牌。

顺子：三张牌，其面值成公差为 1 的等差数列。

面子：刻子或顺子。

一副牌能胡当且仅当：

1. 这副牌有 14 张。
2. 这副牌可以被分为（4 个面子 + 1 个对子）或（7 个对子）。

现在你手里有 13 张牌，每次你随机从牌堆里摸一张牌，问你手中的牌能产生一个能胡的子集的期望摸牌次数。

$n \leq 100$n≤100。答案对 998244353 取模。

题解

首先，对于这种类型的期望题有一个很经典的转化，就是算不合法（不能胡）的方案数。如果你摸了 $i$i 张牌还不能胡的摸牌排列数是 $\text{ans}_i$ansi​，则最终的答案就是

$\sum_{i=0}^{4n-13} \frac{\text{ans}_i}{(4n-13)^{\underline{i}}}$i=0∑4n−13​(4n−13)i​ansi​​

然后，我们要明确怎么描述一副牌。

很明显，牌的顺序与它能不能胡无关。那么我们就可以用桶来存牌。令 $\text{buc}_i$buci​ 为面值 $i$i 的牌的张数。

那么我们很明显可以令 $\text{dp1}_{i,j,\text{state}}$dp1i,j,state​ 表示只考虑前 $i$i 种面值的麻将，摸了 $j$j 张牌，当前拥有的所有牌处于某种状态 $\text{state}$state 下的摸牌排列数。其中 $\text{state}$state 需要足够少，且能鲜明判断当前状态关于胡牌的特征。

这个的转移可以结合插入的思想：已知一个排列，可以通过往里面插入来产生新的排列。可以用插板法得出转移时所需的组合系数。

为了处理 $\text{state}$state 我们考虑：给你一副牌，如何判断它能不能胡。

题面告诉我们有两种胡牌方案。

对于第一种，考虑到一个顺子只会由三种面值相邻的牌拼成，且 3 个同样的顺子可以视为三个面值相邻的刻子，我们可以基于这一点设立一个 dp。

令 $\text{dp2}_{0/1,i,j,k}$dp20/1,i,j,k​ 代表现在 选/没选对子，只考虑前 $i$i 种面值，选了 $j$j 个面值 $i-1$i−1 与 $i$i 的组合（意图凑成 $(i-1,i,i+1)$(i−1,i,i+1) 顺子），选了 $k$k 个面值 $i$i（意图凑成 $(i,i+1,i+2)$(i,i+1,i+2) 顺子），这一情况下的最大凑成的面子数。其中，$j,k \leq 2$j,k≤2。

如果按刷表的想法看，可以根据下一种面值的张数 $$\text{buc}_{i+1}$buci+1​ 决定转移。在刨去用于凑顺子的 $j+k$j+k 张牌后，你可以支配剩余的 $\text{buc}_{i+1}-j-k$buci+1​−j−k 张牌。这些牌可以用于构成对子（第一维为 0 且剩余 $\ge 2$≥2），构成刻子（剩余 $\ge 3$≥3），或者用于凑顺子（作为下一状态的 $k$k）。分配方案很有限。

$\qquad\qquad$

（上述图示中，左侧为转移时构成刻子的方案，右侧为转移时构成对子的方案。由于我们要让之前定下的状态有意义，我们必须安排一个三万凑成顺子。）

对于第二种，我们设立一个值 $\text{cnt}$cnt，每到达一种新的面值且其张数 $\ge 2$≥2，我们就令 $\text{cnt}$cnt 加一。

这样的话，一旦存在一个 $\text{dp2}$dp2 数组中的值 $\ge 4$≥4 且第一维为 1， 或者 $\text{cnt}$cnt 达到 7，我们就可以认定这副牌是胡的。

由此可以看出，对于 $i$i 固定的一个矩阵 $\text{dp2}_{0/1,j,k}$dp20/1,j,k​，对于下一种面值的每一种张数，这个矩阵必然转移为一个特定的新矩阵。我们可以用 $\text{cnt}$cnt 和上述这个矩阵拼成一个结构体 $\text{Mahjong}$Mahjong，作为自动机的节点，结合 bfs 与 map 设立转移自动机。由于状态个数有限（每个状态下存的值 $\leq 4$≤4），必然会成环或终止，所以这个自动机是可以构建的。实测节点个数 $\text{node} \approx 3600$node≈3600。

把当前所在的自动机节点编号作为 $\text{state}$state，外部转移时只需要将下一种面值的张数扔进自动机就能跑出转移到的下一个 $\text{state}$state。

复杂度 $O \left( \text{node} \times \log \text{node} + \text{node} \times n^2 \right)$O(node×lognode+node×n2)

坑点

构建自动机时，转移的矩阵每个位置要对 4 取 min，不然会产生无限转移；

同一种面值的不同牌是不一样的，转移时要乘下降幂。

不要统计已经胡了的情况，也不要从已经胡了的状态往外转移。

代码

#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
using namespace std;
const int N=101,NDC=3700,MOD=998244353;
inline int qpow(int base,int expo)
{
	int ret=1;
	while(expo)
	{
		if(expo&1) ret=1ll*base*ret%MOD;
		base=1ll*base*base%MOD;
		expo>>=1;
	}
	return ret;
}
struct node
{
	int cnt;
	int dp[2][3][3];
	bool operator < (const node &a) const
	{
		if(cnt!=a.cnt) return cnt<a.cnt;
		for(int i=0;i<2;i++)
			for(int j=0;j<3;j++)
				for(int k=0;k<3;k++)
					if(dp[i][j][k]!=a.dp[i][j][k]) return dp[i][j][k]<a.dp[i][j][k];
		return false;
	}
};
int buc[N],nxt[NDC][5],dp[2][N*4][NDC],ed[NDC];
map<node,int> link;
int ndc,h,t;
node q[NDC];
inline bool check(node a){return a.cnt>=7||a.dp[1][0][0]>=4;}
inline node trans(node a,int ct)
{
	node ret;
	ret.cnt=a.cnt+(ct>=2);
	memset(ret.dp,-1,sizeof(ret.dp));
	int i,j,k;
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(a.dp[0][i][j]==-1) continue;
			for(k=0;k<3&&i+j+k<=ct;k++)
			{
				int rem=ct-i-j-k;
				if(rem>=2) ret.dp[1][j][k]=min(4,max(ret.dp[1][j][k],a.dp[0][i][j]+i));
				ret.dp[0][j][k]=min(4,max(ret.dp[0][j][k],a.dp[0][i][j]+i+(rem>=3)));
				if(a.dp[1][i][j]!=-1) ret.dp[1][j][k]=min(4,max(ret.dp[1][j][k],a.dp[1][i][j]+i+(rem>=3)));
			}
		}
	}
	return ret;
}
void bfs()
{
	node st;
	st.cnt=0,memset(st.dp,-1,sizeof(st.dp));
	st.dp[0][0][0]=0;
	link[st]=++ndc,q[t++]=st;
	while(h<t)
	{
		node now=q[h++];
		if(check(now)) continue;
		for(int i=0;i<=4;i++) 
		{
			node to=trans(now,i);
			if(!link[to])
			{
				nxt[link[now]][i]=link[to]=++ndc;
				maxx=max(to.dp[0][0][0],maxx);
				if(check(to)) ed[ndc]=1;
				q[t++]=to;	
			}
			else nxt[link[now]][i]=link[to];
		}
	}
}
int C[N*4][N*4],dfac[N*4],A[5][5];
int main()
{
	bfs();
	int n,i,j,k,l;
	scanf("%d",&n);
	dfac[0]=1;
	for(i=0;i<=4;i++)
	{
		A[i][0]=1;
		for(j=1;j<=i;j++) A[i][j]=A[i][j-1]*(i-j+1);
	}
	for(i=1;i<=n*4;i++) dfac[i]=1ll*dfac[i-1]*qpow(n*4-13-i+1,MOD-2)%MOD;
	for(i=0;i<=n*4;i++) C[0][i]=1;
	for(i=1;i<=n*4;i++)
	{
		C[i][i]=1;
		for(j=i+1;j<=n*4;j++) C[i][j]=(C[i][j-1]+C[i-1][j-1])%MOD;
	}
	for(i=1;i<=13;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		buc[x]++;
	}
	dp[0][0][1]=1;
	for(i=1;i<=n;i++)
	{
		int tmp=i&1;
		for(j=0;j<=(i-1)*4;j++)
		{
			for(k=1;k<=ndc;k++)
			{
				if(!dp[tmp^1][j][k]) continue;
				if(ed[k]) continue; 
				for(l=0;l<=4-buc[i];l++)
				{
					dp[tmp][j+l][nxt[k][l+buc[i]]]=
					(0ll+dp[tmp][j+l][nxt[k][l+buc[i]]]+1ll*dp[tmp^1][j][k]*C[j][l+j]%MOD*A[4-buc[i]][l]%MOD)%MOD;
				}
				dp[tmp^1][j][k]=0;
			}
		}
	}
	int tp=n&1,ans=0;
	for(i=0;i<=n*4;i++)
	{
		int tans=0;
		for(j=1;j<=ndc;j++)
		{
			if(ed[j]) continue;
			tans=(tans+dp[tp][i][j])%MOD;
		}
		tans=1ll*tans*dfac[i]%MOD;
		ans=(ans+tans)%MOD;
	}
	printf("%d",ans);
	return 0;
}