题解 P5279 【[ZJOI2019]麻将】

~~麻雀って、楽しいね。~~ 显然比zjoi2018d1t1简单并且好写多了…… 虽然题意很奇怪但是做法还是很传统的 _______ ## 前置芝士：dp套dp 其实不会这个技术也行不过会了最好 # 本题题解 显然给出一个牌的集合$S$,我们仅仅关心每一种牌出现了多少次 换句话讲2333这幅牌和3233这幅牌是一样的 那么我们可以将一个副表示成一个长度为n的字符串，其中这个字符串的第i位表示第i种牌出现了几次 比如说2333556这幅牌转化成字符串就是013021 现在我们成功的将一副牌压成了一个长度为n的字符串了，让我们来考虑一下如何识别一个字符串能不能胡 那么我们可以尝试造个自动机出来，使得这个自动机可以识别一副胡了的牌,造自动机的方式有很多种，其中一种就是把dp强行改成自动机 那么我们尝试设计一个dp,注意到我们将一副牌映射成一个字符串之后，牌的编号是连续的，那么我们可以这样设计一个$dp(i,j,k,0/1)$表示处理完了第i种编号的牌，我们**预留**了j对形如$i-1,i$的牌，和$k$个编号为$i$的牌,$0/1$表示之前的决策过程当中有没有**预留**过对子，dp当中存储的值是这种情况下的最大面子数 注意到三个相同的顺子可以被算成三个连续的刻子,那么我们会发现$j$和$k$这两维都不会超过2 dp的转移也十分简单,假设来了$x$张$i+1$编号的牌，首先原来的$j,k$之和必须小于等于x,因为要满足原来的预留情况,处理完预留情况之后我们枚举留下几张x作为新顺子的开始,剩下的x尝试去组刻子,同时一开始预留的j张$(i-1,i)$可以和$i+1$凑出$j$个顺子来,按照定义转移一下就可以了 当然我们还要枚举预留还是不预留对子，这个部分也很简单 这样我们dp我们可以dp出这张牌是不是传统胡牌了 接下来考虑判定七对子，这个特判一下就行了，如果有7个及以上的编号有对子就可以凑一个七对子出来 那么我们怎么造自动机呢? 很简单，我们把$dp(j,k,0/1)$这个三维数组直接当成自动机的节点，节点之间的转移就是普通dp的转移，为了压缩节点数目，我们认为dp数组当中的任意一个值都不能超过$4$ 这样我们就可以搞定传统胡牌了，加上七对子的情况只需要在节点上单独记一个变量表示对子的数目即可了 一个节点是胡的当且仅当dp值当中有大于等于4的位置，或者出现了7个**不同的对子**~~(听说有些地方规则七对子带杠?)~~ 最后我们为胡牌的状态单开一个节点，这个节点无论输入什么都会走回自己 建这个自动机可以用map存储每个状态的编号,然后使用bfs来构建自动机 由于将所有胡牌的节点缩成了一个点,因此点数会比网上题解的点数要少，具体来讲是$2092$个节点，你可以使用这个数字校验一下你的搜索有没有写错 现在我们有了自动姬就可以dp了 我们希望求出这副牌的最小胡牌巡目数的期望，根据一个期望题上经典的转化，我们只需要算出已经摸了$i$张牌还是不胡的方案数加起来，除以$(4n-13)!$最后把答案加1就是答案了(加1是因为本来算的是胡牌时间大于等于i的方案数，我们强行变成了算胡牌时间大于i-1的方案数) 我们可以设$f(i)$表示摸了i张牌之后还不胡的牌的集合数目 那么我们最终的答案就是 $$1+\frac{\sum_{i=1}^{4n-13}f(i)i!(4n-13-i)!}{(4n-13)!}$$ 现在考虑怎么算$f(i)$就行了 也很简单$dp(k,n,j)$表示字符串长度为k,摸了n张牌，走到自动姬上点j的方案数 转移方程就是枚举字符串的第$k+1$位是什么，假如第$k+1$种牌还剩$p$张,我们放了$t$张，那么转移的时候乘一个${p \choose t}$的系数即可 想卡一下空间的话可以滚动数组实现这个dp (应该比直接dp排列的做法好写很多) 复杂度$O(2092×n^2)$常数不大可以通过本题 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #include<map> #include<queue> using namespace std;const int N=4100;const int M=4100; typedef unsigned long long ll;const ll mod=998244353; struct data//转移用的矩阵类 { int dp[3][3]; inline int* operator [](const int& x){return dp[x];} data() { for(int i=0;i<3;i++) for(int j=0;j<3;j++)dp[i][j]=-1; } friend bool operator <(data a,data b) { for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(a[i][j]!=b[i][j])return a[i][j]<b[i][j]; return false; } friend bool operator !=(data a,data b) { for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(a[i][j]!=b[i][j])return true;return false; } inline void trs(data& c,int del) { for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(dp[i][j]!=-1) for(int k=0,rem=del-i-j;k<3&&i+j+k<=del;k++,rem--) c[j][k]=max(c[j][k],min(i+dp[i][j]+rem/3,4)); } inline bool ckhu() { for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(dp[i][j]>=4)return true;return false; } }; struct nod//自动机节点 { data is_pair[2];int cnt_pair; friend bool operator <(nod a,nod b) { if(a.cnt_pair!=b.cnt_pair)return a.cnt_pair<b.cnt_pair; if(a.is_pair[0]!=b.is_pair[0])return a.is_pair[0]<b.is_pair[0]; if(a.is_pair[1]!=b.is_pair[1])return a.is_pair[1]<b.is_pair[1]; return false; } inline void clear() {is_pair[0]=data();is_pair[1]=data();cnt_pair=-2333;} inline bool ckhu() { if(cnt_pair>=7){clear();return true;} if(is_pair[1].ckhu()){clear();return true;} return false; } friend nod operator +(nod a,int b) { if(a.cnt_pair==-2333)return a; nod c; if(b>=2)a.is_pair[0].trs(c.is_pair[1],b-2); a.is_pair[0].trs(c.is_pair[0],b); a.is_pair[1].trs(c.is_pair[1],b); c.cnt_pair=a.cnt_pair+(b>=2); c.ckhu(); return c; } }; inline nod stat() { nod res;res.clear();res.cnt_pair=0;res.is_pair[0][0][0]=0; return res; } map <nod,int> mrk;int tot;int mp[M][5];queue <nod> q;int ed; inline void bfs()//搜索 { nod st=stat(); q.push(st);mrk[st]=++tot; while(!q.empty()) { st=q.front();q.pop();int nu=mrk[st]; for(int i=0;i<=4;i++) { nod tw=st+i; if(mrk.count(tw))mp[nu][i]=mrk[tw]; else mp[nu][i]=mrk[tw]=++tot,q.push(tw); } } st.clear();ed=mrk[st]; } ll fac[N];ll inv[N];ll ifac[N]; ll dp[2][440][M];ll* p1[440];ll* p2[440]; ll xs[N];int sum[N];int n; inline void pre() { fac[0]=1;for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod; inv[0]=inv[1]=1;for(int i=2;i<N;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod; ifac[0]=1;for(int i=1;i<N;i++)ifac[i]=ifac[i-1]*inv[i]%mod; } inline void calc()//dp使用了滚动数组 { int cap=n*4-13; for(int i=0;i<=cap;i++)p1[i]=dp[0][i]; for(int i=0;i<=cap;i++)p2[i]=dp[1][i];p1[0][mrk[stat()]]=1; for(int z=1;z<=n;z++) { for(int j=0;j<=4-sum[z];j++)xs[j]=fac[4-sum[z]]*ifac[4-sum[z]-j]%mod*ifac[j]%mod; for(int i=cap;i>=0;i--) { for(int j=1;j<=tot;j++)p2[i][j]=0; for(int j=1;j<=tot;j++) if(p1[i][j]!=0) for(int tmp=0;tmp<=4-sum[z]&&i+tmp<=cap;tmp++) (p2[i+tmp][mp[j][tmp+sum[z]]]+=p1[i][j]*xs[tmp])%=mod; } for(int i=0;i<=cap;i++)swap(p1[i],p2[i]); } } int main() { bfs();pre(); scanf("%d",&n); for(int i=1,w,t;i<=13;i++)scanf("%d%d",&w,&t),sum[w]++; calc(); ll ans=0; for(int p=1,q=4*n-14;p<=4*n-13;p++,q--)//计算答案 for(int j=1;j<=tot;j++) if(j!=ed)(ans+=p1[p][j]*fac[p]%mod*fac[q])%=mod; printf("%lld",ans*ifac[4*n-13]%mod+1); return 0;//拜拜程序~ } ```