题解：P5279 [ZJOI2019] 麻将
MatrixGroup
·
·
题解
前言
非确定性有限状态自动机 \to 确定性有限状态自动机 \to 爆搜有效状态 \to dp。
等等，为什么别的题解里都跑出了 2\,092 或 3\,956 个状态？
题意
有一套只有一种花色的麻将，1\sim n 的数牌各有 4 张。将其随机打乱后，给定前 13 张牌，求最短的包含一个和牌的子集的前缀的长度的期望。和牌型包含基本型（四个面子和一个对子）和七对子（七个不同的对子）。
## 题解
首先转化一下题意。对于取值为正整数的随机变量 $X$，有 $\mathbb E[X]=\sum\limits_{i=0}^{+\infty} \Pr[X>i]$。换言之，我们只需要对于每个 $i$ 求出拿了 $i$ 张牌还没和的概率即可。
考虑先对于一个表示每种牌出现次数的序列 $\{c_i\}$ 设计一个判定和牌的非确定有限状态自动机。对于基本型，记录 $(i,j,k,t)$ 表示当前有 $i$ 个已经完成的面子，$j$ 个待完成的两面搭子，$k$ 个当前牌的单张和是否已经有对子。显然，同一种顺子有三个可以看成同一种刻子有三个，因此一定可以使 $j,k\le 2$，而因为总共最多四个面子，有 $i+j+k\le 4$，因此这样的状态一共有 $54$ 个。对于七对子，记录目前有 $0\sim 7$ 个对子，共有 $8$ 个状态。这就设计好了。
再考虑对于一个表示每种牌出现次数的序列 $\{c_i\}$，如何判定它有没有一个和牌的子集。直接考虑记录它的所有子集能走到的那些状态即可。看似可能有 $2^{62}$ 个状态，但是直觉告诉我们这些状态能否走到一定是非常关联的。（比如，能走到的两个状态一定牌数相同）实际上只有 $\boxed{c=1\,840}$ 个状态。
那么我们就可以 dp。$dp_{i,j,k}$ 表示前 $i$ 种数牌拿了 $j$ 个走到 $k$ 的子集数。注意转移要乘组合数。$i$ 这一维可以滚动掉。这样时间复杂度就是 $O(n^2S)$ 的，可以通过。
## 代码
```cpp
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,del##i##verme=int(n);i<del##i##verme;++i)
#define rep1(i,n) for(int i=1,parano##i##a=int(n);i<=parano##i##a;++i)
typedef long long ll;
using namespace std;
const ll mod1=998244353;
int tp[2222],n0[2222],n1[2222],n2[2222],p[2222],cnt;
int f[2][9][5][5][5];
ll trans(ll state,int ad)
{
ll ret=0;
rep(i,cnt) if((state>>i)&1)
{
if(tp[i]==0)
{
int a=n0[i],x=n1[i],y=n2[i],z=p[i];
if(ad>=x+y)
{
int d=ad-x-y;
a+=x+(d/3);x=y;y=d%3;
if(f[0][a][x][y][z]!=-1) ret|=1ll<<f[0][a][x][y][z];
if(!z&&d>=2)
{
d-=2;if(f[0][n0[i]+n1[i]][n2[i]][d][1]!=-1)
ret|=1ll<<f[0][n0[i]+n1[i]][n2[i]][d][1];
}
}
}
else if(ad==2)
{
if(n0[i]!=7) ret|=2ll<<i;
}
else if(ad==0)
{
ret|=1ll<<i;
}
}
return ret;
}
map<ll,int> id;
int c;ll ft[3141];
int trs[5][3141];
bool ok[3141];
void dfs(ll x)
{
if(id[x]) return ;
id[x]=++c;ft[c]=x;
ll ret=0;
rep(i,5)
{
ret|=trans(x,i);
dfs(ret);
}
}
ll C[405][405];
void init()
{
memset(f,-1,sizeof(f));
rep(a,5) rep(i,3) rep(j,3) rep(k,2) if(a+i+j<=4)
{
tp[cnt]=0;n0[cnt]=a;
n1[cnt]=i;n2[cnt]=j;p[cnt]=k;
f[0][a][i][j][k]=cnt++;
}
rep(i,8)
{
tp[cnt]=1;n0[cnt]=i;
n1[cnt]=n2[cnt]=p[cnt]=0;
f[1][i][0][0][0]=cnt++;
}
dfs((1ll<<f[0][0][0][0][0])|(1ll<<f[1][0][0][0][0]));
rep1(i,c)
{
ll ret=0;
rep(j,5) trs[j][i]=id[ret|=trans(ft[i],j)];
}
rep1(i,c)
{
if(((ft[i]>>f[0][4][0][0][1])&1)||((ft[i]>>f[1][7][0][0][0])&1))
ok[i]=true;
else
ok[i]=false;
}
C[0][0]=1;
rep1(i,400)
{
C[i][0]=C[i][i]=1;
rep1(j,i-1)
{
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod1;
}
}
}
ll qkpw(ll a,ll b)
{
ll r=1;
while(b)
{
if(b&1)r=r*a%mod1;
a=a*a%mod1;
b>>=1;
}
return r;
}
int n,a,b;
int cc[105];
ll dp[405][2005],nw[405][2005];
int main()
{
init();
cin>>n;
rep1(i,13)
{
cin>>a>>b;++cc[a];
}
dp[0][1]=1;
rep1(i,n)
{
memset(nw,0,sizeof(nw));
rep(j,i*4-3) rep1(k,c) if(dp[j][k])
{
for(int l=cc[i];l<=4;++l)
{
nw[j+l][trs[l][k]]+=dp[j][k]*C[4-cc[i]][4-l];
}
}
rep(j,i*4+1) rep1(k,c) dp[j][k]=nw[j][k]%mod1;
}
ll answer=0;
for(int i=13;i<=4*n;++i)
{
ll cur=0;
for(int j=1;j<=c;++j)
{
if(!ok[j]) cur+=dp[i][j];
}
cur%=mod1;
answer=(answer+cur*qkpw(C[4*n-13][i-13],mod1-2))%mod1;
}
cout<<answer<<endl;
return 0;
}
```