洛谷 P5270 [ZJOI2019]麻将

https://www.luogu.com.cn/problem/P5279

Tutorial

https://www.luogu.com.cn/blog/DOF/solution-p5279

考虑对于一副牌如何判断是否胡了.

发现一种数字开头的顺子小于\(3\)个,设\(f(i,0/1,j,k)\) 表示前\(i\)种数字,是否已经选了对子,\(i-1\)开始有\(j\)个顺子,\(i\)开始有\(k\)个顺子时最多的面子数,枚举\(i+1\)选多少个顺子.即可.

那么dp数组可以表示为\(2\)个\(3\times3\)的矩阵,而且还需要知道有\(cnt\)种数字的数量大于等于\(2\),面子数只需要保存至\(4\),\(cnt\)只需要保存至\(7\),那么可以将这\(3\)个元素表示为一个状态,转移就相等于传入\(x\),表示下一种数字的数量.

那么就可以进行dp套dp了,设\(dp(i,j,k)\)表示前\(i\)种数字,状态为\(j\),一共有\(k\)张牌,转移系数很简单,注意一开始就有的数字在排列中的位置是确定的.

统计答案就相当于\(\sum_{a=13} p(a)\),其中\(p(a)\)表示选了前\(a\)张牌还没有胡的概率,也就是\(\dfrac {\sum[bad(j)]dp(n,j,a)}{(4n-13)^{\underline{a-13}}}\) .其中\(bad(j)=1\)若\(j\)状态无法胡牌.

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define inver(a) power(a,mod-2)
#define fi first
#define se second
using namespace std;
inline char gc() {
//	return getchar();
	static char buf[100000],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void rd(T &x) {
	x=0; int f=1,ch=gc();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=gc();}
	x*=f;
}
template<class T> inline bool Cmax(T &x,T y) {return x<y?x=y,1:0;}
typedef long long ll;
const int mod=998244353;
const int maxn=100+5,maxs=4000,MAXN=maxn*4;
int n,N,c[maxn];
int ncnt,good[maxs],tp[maxs][5];
int dp[maxn][maxs][MAXN];
int C[MAXN][MAXN],fac[MAXN],inv[MAXN];
inline int add(int x) {return x>=mod?x-mod:x;}
ll power(ll x,ll y) {
	ll re=1;
	while(y) {
		if(y&1) re=re*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return re;
}
struct node {
	int a[3][3];
	node() {memset(a,-1,sizeof(a));}
	bool operator <(const node &other) const {
		for(int i=0;i<3;++i) for(int j=0;j<3;++j) {
			if(a[i][j]!=other.a[i][j]) return a[i][j]<other.a[i][j];
		}
		return 0;
	}
	void Max(node other) {
		for(int i=0;i<3;++i) for(int j=0;j<3;++j) Cmax(a[i][j],other.a[i][j]);
	}
	friend node trans(node u,int x) {
		node re;
		for(int i=0;i<3;++i) for(int j=0;j<3;++j) if(u.a[i][j]!=-1) {
			for(int k=0;k<3&&i+j+k<=x;++k) {
				Cmax(re.a[j][k],min(4,u.a[i][j]+i+(x-i-j-k)/3));
			}
		}
		return re;
	}
};
struct state {
	pair<node,node> dp; int cnt; 
	state() {dp.fi.a[0][0]=cnt=0;}
	bool operator <(const state &other) const {
		if(cnt!=other.cnt) return cnt<other.cnt;
		return dp<other.dp;
	}
	bool judge() {
		if(cnt==7) return 1;
		for(int i=0;i<3;++i) for(int j=0;j<3;++j) {
			if(dp.se.a[i][j]==4) return 1;
		}
		return 0;
	}
	friend state trans(state u,int x) {
		if(x>=2&&u.cnt<7) ++u.cnt;
		u.dp.se=trans(u.dp.se,x);
		if(x>=2) u.dp.se.Max(trans(u.dp.fi,x-2));
		u.dp.fi=trans(u.dp.fi,x);
		return u;
	}
} rec[maxs];
map<state,int> id;
void dfs(state u) {
	if(id.count(u)) return;
	rec[id[u]=++ncnt]=u;
	good[ncnt]=u.judge();
	for(int i=0;i<=4;++i) dfs(trans(u,i));
}
void init() {
	dfs(state());
	for(int i=1;i<=ncnt;++i) for(int j=0;j<=4;++j) {
		tp[i][j]=id[trans(rec[i],j)];
	}
	for(int i=0;i<=N;++i) {
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;++j) C[i][j]=add(C[i-1][j-1]+C[i-1][j]);
	}
	fac[0]=1;
	for(int i=1;i<=N;++i) fac[i]=(ll)fac[i-1]*i%mod;
	inv[N]=inver(fac[N]);
	for(int i=N;i>=1;--i) inv[i-1]=(ll)inv[i]*i%mod;
}
int main() {
	rd(n),N=n*4;
	for(int i=0;i<13;++i) {
		int w,t; rd(w),rd(t);
		++c[w];
	}
	init();
	dp[0][1][0]=1;
	for(int i=1,sum=0;i<=n;++i) {
		sum+=c[i];
		for(int j=1;j<=ncnt;++j) for(int k=c[i];k<=4;++k) {
			int *u=dp[i][tp[j][k]],*v=dp[i-1][j];
			int r=(ll)C[4-c[i]][k-c[i]]*fac[k-c[i]]%mod;
			for(int h=0;h+k<=N;++h) if(v[h]) {
				u[h+k]=(u[h+k]+(ll)v[h]*r%mod*C[h+k-sum][k-c[i]])%mod;
			}
		}
	}
	int an=0;
	for(int i=13,d=1;i<=N;++i) {
		int re=0;
		for(int j=1;j<=ncnt;++j) if(!good[j]) re=add(re+dp[n][j][i]);
		an=(an+(ll)re*inver(d))%mod;
		d=(ll)d*(N-i)%mod;
	}
	printf("%d\n",an);
	return 0;
}