ZJOI2019 麻将

ZJOI2019 麻将
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说ZJOI2019 麻将,希望能够帮助大家进步!!!

一道清真好题,只是之前没有接触过,才感觉非常困难。
感谢yn大佬。

我的做法是dp套dp的做法。
首先如果你有一个麻将自动机,
这个自动机有若干节点,以及节点之间的转移边,以及一个起始状态节点,和一个终止状态集合。

终止状态集合中的节点代表胡了。
你可以给这个自动机新添加一种花色,麻将的数量在0~4之间,然后沿着转移边走到下一个状态。

如果你有这样一个自动机,那么考虑一个dp,\(f[i][j][k]\)表示考虑了前\(i\)种花色,选了\(j\)张麻将,在自动机的\(k\)节点时的无序集合数。
然后一个一定长度的无序集合,映射到相同个数的排列数。
就可以愉快的算出答案了。

当然期望按照套路转化成还未结束的概率和。

丑陋的代码

#include <bits/stdc++.h> using namespace std; typedef long long i64; const int N=105; const int MM=4000; const int M=998244353; namespace{ void Addt(int &x,int y){ (x+=y)>=M?x-=M:0; } int mul(int x,int y){ return (i64)x*y%M; } int fp(int x,int y){ int ret=1; for (; y; y>>=1,x=mul(x,x)) if (y&1) ret=mul(ret,x); return ret; } } struct st{ int a[3][3]; st(){ } st(int x){ for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) a[i][j]=x; } st operator +(const st &_) const{ st ret; for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) ret.a[i][j]=max(a[i][j],_.a[i][j]); return ret; } st operator +(const int &num) const{ st ret(-1); for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) for (int k=0; k<3&&i+j+k<=num; ++k){ if (a[i][j]==-1) continue; ret.a[j][k]=min(max(ret.a[j][k],a[i][j]+(num-k-i-j)/3+i),4); } return ret; } bool operator <(const st &_) const{ for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) if (a[i][j]!=_.a[i][j]) return a[i][j]<_.a[i][j]; return 0; } bool operator !=(const st &_) const{ for (int i=0; i<3; ++i) for (int j=0; j<3; ++j) if (a[i][j]!=_.a[i][j]) return 1; return 0; } }; map<st,int> mst; struct mj{ st f,g; int cnt;//number of different dui zi bool operator <(const mj &_) const{ if (cnt!=_.cnt) return cnt<_.cnt; if (f!=_.f) return f<_.f; return g<_.g; } mj operator +(const int &a) const{ mj ret=*this; if (a>=2){ ret.cnt=min(ret.cnt+1,7); ret.g=(ret.g+a)+(ret.f+(a-2)); } else ret.g=ret.g+a; ret.f=ret.f+a; return ret; } bool ri(){ if (cnt>=7) return 1; //care return g.a[0][0]>=4; } }m_j[MM]; map<mj,int> mmj; int tots,totm; void Dfscomplicated(const st &&s){ if (mst.count(s)) return; mst[s]=++tots; for (int i=0; i<=4; ++i){ Dfscomplicated(s+i); } } void Dfshdaewr(const mj &&m){ //getchar(); if (mmj.count(m)) return; //cerr<<"Dfshdaewr"<<" "<<totm<<" "<<m.cnt<<" "<<mst[m.f]<<" "<<mst[m.g]<<" "<<(mmj.find(m)==mmj.end())<<endl; mmj[m]=++totm; //cerr<<mmj[m]<<endl; m_j[totm]=m; for (int i=0; i<=4; ++i){ Dfshdaewr(m+i); } } st zst(){ st ret=st(-1); ret.a[0][0]=0; return ret; } mj zmj(){ mj ret; ret.f=zst(); ret.g=st(-1); ret.cnt=0; return ret; } int binomial[5][5],trans[MM][5]; void Prework(){ for (int i=0; i<=4; ++i){ binomial[i][0]=1; for (int j=1; j<=i; ++j) Addt(binomial[i][j]=binomial[i-1][j-1],binomial[i-1][j]); } //cerr<<"???"<<endl; Dfscomplicated(zst()); //cerr<<"????"<<tots<<endl; Dfshdaewr(zmj()); //cerr<<"?????"<<totm<<endl; for (int i=1; i<=totm; ++i) for (int j=0; j<=4; ++j){ trans[i][j]=mmj[m_j[i]+j]; //cerr<<i<<" "<<j<<" "<<trans[i][j]<<endl; } //cerr<<"Preworkend"<<endl; } int n,usd[N],f[N][N*4][MM]; int main(){ cin>>n; for (int i=1; i<=13; ++i){ int x,y; cin>>x>>y; ++usd[x]; } Prework(); //cerr<<"!!!!!"<<binomial[0][0]<<endl; f[0][0][1]=1; for (int i=0; i<n; ++i) for (int j=0; j<=i*4; ++j) for (int d=1; d<=totm; ++d) if (f[i][j][d]){ //cerr<<i<<" "<<j<<" "<<d<<" "<<f[i][j][d]<<" "<<m_j[d].ri()<<endl; //getchar(); int tmp=f[i][j][d]; for (int k=usd[i+1]; k<=4; ++k){ //cerr<<"trans:"<<k<<" "<<trans[d][k]<<endl; Addt(f[i+1][j+k][trans[d][k]],mul(tmp,binomial[4-usd[i+1]][k-usd[i+1]])); } } //cerr<<"????"<<endl; int ans=0; for (int j=13; j<=n*4; ++j){ int sum=0; int nend=0; for (int i=1; i<=totm; ++i){ Addt(sum,f[n][j][i]); //if (f[n][j][i]) cerr<<j<<" "<<i<<" "<<f[n][j][i]<<" "<<ans<<" "<<sum<<" "<<nend<<endl; if (!m_j[i].ri()) Addt(nend,f[n][j][i]); } Addt(ans,mul(nend,fp(sum,M-2))); } cout<<ans; }

转载于:https://www.cnblogs.com/Yuhuger/p/10668374.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29917

发表评论