原題傳送門

希望這題不會(huì)讓你對(duì)麻將的熱愛(ài)消失殆盡

我們珂以統(tǒng)計(jì)每種牌出現(xiàn)的次數(shù)，不需要統(tǒng)計(jì)是第幾張牌

判一副牌能不能和，類似這道題

對(duì)于這題：

設(shè)\(f[i][j][k][0/1]\)表示前\(i\)種牌，順子\((i-1,i,i+1)\)出現(xiàn)了\(j\)次，順子\((i,i+1,i+2)\)出現(xiàn)了\(k\)次，有/沒(méi)有雀頭的最多面子數(shù)。轉(zhuǎn)移比較簡(jiǎn)單

我們珂以發(fā)現(xiàn)\(i\)這維不太重要，強(qiáng)制dp值不超過(guò)\(4\)（超過(guò)\(4\)也沒(méi)有用），雀頭數(shù)不超過(guò)\(7\)（類似），爆搜珂以搜出本質(zhì)不同的狀態(tài)一共有\(2091\)個(gè)

珂以在每個(gè)狀態(tài)珂以在后面加\(x \in [0,4]\)張點(diǎn)數(shù)+1的牌，這珂以構(gòu)成一個(gè)自動(dòng)機(jī)，我們叫她和牌自動(dòng)機(jī)

我們每得到一個(gè)狀態(tài)，珂以在和牌自動(dòng)機(jī)上走，判斷是否能和

我們?cè)O(shè)\(dp[i][j][k]\)表示看到前\(i\)種牌，在和牌自動(dòng)機(jī)上的\(j\)狀態(tài)，已經(jīng)摸了\(k\)張牌，不胡的種類數(shù)，最后算一下期望就珂以了

我們珂以用滾動(dòng)數(shù)組把\(i\)滾掉優(yōu)化空間

#include <bits/stdc++.h> #define mod 998244353 #define N 405 #define getchar nc using namespace std; inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline int read() {register int x=0,f=1;register char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f; } inline void write(register int x) {if(!x)putchar('0');if(x<0)x=-x,putchar('-');static int sta[20];register int tot=0;while(x)sta[tot++]=x%10,x/=10;while(tot)putchar(sta[--tot]+48); } inline int Min(register int a,register int b) {return a<b?a:b; } inline int Max(register int a,register int b) {return a>b?a:b; } struct node{int f[3][3][2],cnt;inline void init(){memset(f,-1,sizeof(f));f[0][0][0]=cnt=0;}inline int hu(){if(cnt>=7)return 1;for(register int i=0;i<3;++i)for(register int j=0;j<3;++j)if(f[i][j][1]>=4)return 1;return 0;} }rt,S[2100]; bool operator < (node a,node b){if(a.cnt!=b.cnt)return a.cnt<b.cnt;for(register int i=0;i<3;++i)for(register int j=0;j<3;++j)for(register int k=0;k<2;++k)if(a.f[i][j][k]!=b.f[i][j][k])return a.f[i][j][k]<b.f[i][j][k];return 0; } int tot=0; map<node,int> ma; inline node trans(register node u,register int w) {node v;v.init();v.cnt=Min(u.cnt+(w>=2),7);for(register int i=0;i<3;++i)for(register int j=0;j<3;++j){if(~u.f[i][j][0]){for(register int k=0;k<3&&i+j+k<=w;++k) v.f[j][k][0]=Max(v.f[j][k][0],Min(u.f[i][j][0]+i+(w-i-j-k>=3),4));if(w>=2)for(register int k=0;k<3&&i+j+k<=w-2;++k)v.f[j][k][1]=Max(v.f[j][k][1],Min(u.f[i][j][0]+i,4));}if(~u.f[i][j][1])for(register int k=0;k<3&&i+j+k<=w;++k)v.f[j][k][1]=Max(v.f[j][k][1],Min(u.f[i][j][1]+i+(w-i-j-k>=3),4));}return v; } inline void build(register node u) {if(u.hu())return;if(ma.find(u)!=ma.end())return;ma[u]=++tot;S[tot]=u;for(register int i=0;i<=4;++i)build(trans(u,i)); } int n,s[N],ans; int fac[N],inv[N],invf[N],tr[2100][5],f[2][2100][N]; inline int C(register int n,register int m) {return 1ll*fac[n]*invf[m]%mod*invf[n-m]%mod; } int main() {rt.init();build(rt);invf[0]=inv[0]=inv[1]=fac[0]=1;for(register int i=1;i<N;++i)fac[i]=1ll*fac[i-1]*i%mod;for(register int i=2;i<N;++i)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;for(register int i=1;i<N;++i)invf[i]=1ll*invf[i-1]*inv[i]%mod;n=read();for(register int i=1;i<=13;++i)++s[read()],read();for(register int i=1;i<=tot;++i)for(register int j=0;j<=4;++j)tr[i][j]=ma[trans(S[i],j)];f[0][1][0]=1;for(register int i=1,sum=0;i<=n;++i){int now=i&1,pre=now^1;memset(f[now],0,sizeof(f[now]));for(register int j=1;j<=tot;++j)for(register int k=s[i];k<=4;++k){if(!tr[j][k])continue;int w=1ll*C(4-s[i],k-s[i])*fac[k-s[i]]%mod;for(register int l=0;l<=4*n-k;++l){if(!f[pre][j][l])continue;f[now][tr[j][k]][l+k]=(0ll+f[now][tr[j][k]][l+k]+1ll*f[pre][j][l]*w%mod*C(k+l-sum-s[i],k-s[i])%mod)%mod;}}sum+=s[i];}for(register int i=13,w=1;i<=4*n;++i){int now=0;for(register int j=1;j<=tot;++j)now=(0ll+now+f[n&1][j][i])%mod;ans=(0ll+ans+1ll*now*w%mod)%mod;w=1ll*w*inv[4*n-i]%mod;}write(ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/yzhang-rp-inf/p/10993547.html

總結(jié)

以上是生活随笔為你收集整理的【题解】Luogu P5279 [ZJOI2019]麻将的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。