Loj #3042. 「ZJOI2019」麻将
题目描述
九条可怜是一个热爱打麻将的女孩子。因此她出了一道和麻将相关的题目，希望这题不会让你对麻将的热爱消失殆尽。
今天，可怜想要打麻将，但是她的朋友们都去下自走棋了，因此可怜只能自己一个人打。可怜找了一套特殊的麻将，它有 \(n(n \ge 5)\) 种不同的牌，大小分别为 \(1\) 到 \(n\)，每种牌都有 \(4\) 张。
定义面子为三张大小相同或者大小相邻的麻将牌，即大小形如 \(i, i, i(1 \le i \le n)\) 或者\(i, i + 1, i + 2(1 \le i \le n − 2)\)。定义对子为两张大小相同的麻将牌，即大小形如 \(i, i(1 \le i \le n)\)。
定义一个麻将牌集合 \(S\) 是胡的当且仅当它的大小为 \(14\) 且满足下面两个条件中的至少一个：
- \(S\) 可以被划分成五个集合 \(S_1\) 至 \(S_5\)。其中 \(S_1\) 为对子，\(S_2\) 至 \(S_5\) 为面子。
- \(S\) 可以被划分成七个集合 \(S_1\) 至 \(S_7\)，它们都是对子，且对应的大小两两不同。
举例来说，下列集合都是胡的（这儿只标记了大小）：
- \(\{1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9\}\)
- \(\{1, 1, 2, 2, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8\}\)
- \(\{1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7\}\)
而下列集合都不是胡的：
- \(\{1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9\}\)
- \(\{1, 1, 1, 1, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8\}\)
- \(\{1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9, 11\}\)
可怜先摸出了 \(13\) 张牌，并把剩下的 \(4n − 13\) 张牌随机打乱。打乱是等概率随机的，即所有 \((4n − 13)!\) 种排列都等概率出现。
对于一个排列 \(P\)，可怜定义 \(S_i\) 为可怜事先摸出的 \(13\) 张牌加上 \(P\) 中的前 \(i\) 张牌构成的集合，定义 \(P\) 的权值为最小的 \(i\) 满足 \(S_i\) 存在一个子集是胡的。如果你对麻将比较熟悉，不难发现 \(P\) 的权值就是理论上的最早胡牌巡目数。注意到 \(n \ge 5\) 的时候，\(S_{4n−13}\) 总是存在胡的子集的，因此 \(P\) 的权值是良定义的。
现在可怜想要训练自己的牌效，因此她希望你能先计算出 \(P\) 的权值的期望是多少。
\(\\\)
神仙的\(DP\)套\(DP\)题。
首先想如何判断一个局面是胡的。对于第一种胡牌方式，我们用\(DP\)来维护。设\(f_{i,j,k,0/1}\)表示是考虑了前\(i\)种麻将，以\(i-1\)开头的面子有\(j\)个，以\(i\)开头的面子有\(k\)个，是否有对子的最大面子数。注意这里以\(i-1\)开头以及以\(i\)开头的面子都是还没有生效的，要放了大小为\(i+1\)的麻将后才能判断。转移的时候就枚举第\(i\)张牌放入了\(x\)个，枚举几种情况就好了。
对于第二种胡牌方式，直接记\(cnt\)表示不同的顺子个数就行了。
显然\(cnt\)不能达到\(7\)，\(f_{i,j,k,1}\)的最大值不能达到\(4\)。于是我们就暴力将\(cnt\)以及\(f\)数组作为状态。如果\(f\)超过\(4\)，就存成\(4\)，\(cnt\)同理，以减小状态量。可以算出合法状态最多\(2091\)个。
然后就是\(DP\)计数了。设\(F_{i,j,S}\)表示考虑了前\(i\)种麻将，一共摸了\(j\)张牌，\(DP\)状态为\(S\)时还未胡牌的概率。转移的时候枚举额外摸了多少张\(i\)麻将（除去底牌）。
我们的定义是还未胡牌而不是已经胡牌的原因是我们枚举的麻将顺序是编号，不是模到这张牌的时间，所以对于一个胡牌的局面，我们不知道他到底是什么时候胡的。
利用一个经典的期望转概率的公式就可以算出答案了：
=\sum P(x\geq i)
\]
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 105
#define M 405
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
const ll mod=998244353;
ll ksm(ll t,ll x) {
ll ans=1;
for(;x;x>>=1,t=t*t%mod)
if(x&1) ans=ans*t%mod;
return ans;
}
ll fac[M],ifac[M];
ll C(int n,int m) {return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
struct info {
int f[3][3][2];
int cnt;
info() {memset(f,-1,sizeof(f));f[0][0][0]=cnt=0;}
bool operator <(const info &a)const {
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int k=0;k<2;k++)
if(f[i][j][k]!=a.f[i][j][k]) return f[i][j][k]<a.f[i][j][k];
return cnt<a.cnt;
}
bool chk() {
if(cnt>=7) return 0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(f[i][j][1]>=4) return 0;
return 1;
}
info trans(int x) {
info tem;
tem.cnt=cnt+(x>=2);
for(int i=0;i<3;i++) {
for(int j=0;j<3;j++) {
for(int k=0;k<2;k++) {
if(f[i][j][k]==-1) continue ;
for(int t=0;t<3&&i+j+t<=x;t++) {
tem.f[j][t][k]=max(tem.f[j][t][k],f[i][j][k]+i+(x-i-j-t>=3));
}
if(!k) {
for(int t=0;t<3&&i+j+t<=x-2;t++) {
tem.f[j][t][1]=max(tem.f[j][t][1],f[i][j][k]+i);
}
}
}
}
}
for(int k=0;k<2;k++)
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
tem.f[i][j][k]=min(tem.f[i][j][k],4);
return tem;
}
};
int n;
map<info,int>id;
info mj[4005];
int tot;
int Had[N];
info tem;
int trans[4005][5];
void dfs(info now) {
if(!now.chk()) return ;
id[now]=++tot;
mj[tot]=now;
for(int i=0;i<=4;i++) {
info tem=now.trans(i);
if(id.find(tem)==id.end()) dfs(tem);
trans[id[now]][i]=id[tem];
}
}
ll f[N][M][2100];
int main() {
fac[0]=1;
for(int i=1;i<=400;i++) fac[i]=fac[i-1]*i%mod;
ifac[400]=ksm(fac[400],mod-2);
for(int i=399;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
info x;
dfs(x);
n=Get();
for(int i=1;i<=13;i++) {
int w=Get(),t=Get();
Had[w]++;
}
f[0][0][1]=1;
for(int i=0;i<n;i++) {
for(int j=0;j<=i*4;j++) {
for(int k=1;k<=tot;k++) {
if(!f[i][j][k]) continue ;
for(int t=Had[i+1];t<=4;t++) {
if(trans[k][t]) (f[i+1][j+t-Had[i+1]][trans[k][t]]+=f[i][j][k]*C(4-Had[i+1],t-Had[i+1])%mod*C(j+t-Had[i+1],t-Had[i+1])%mod*fac[t-Had[i+1]])%=mod;
}
}
}
}
ll ans=0;
for(int i=0;i<=4*n-13;i++) {
for(int j=1;j<=tot;j++) {
(ans+=f[n][i][j]*ifac[4*n-13]%mod*fac[4*n-13-i])%=mod;
}
}
cout<<ans;
return 0;
}