博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷P5279 [ZJOI2019]麻将(乱搞+概率期望)
阅读量:5827 次
发布时间:2019-06-18

本文共 2855 字,大约阅读时间需要 9 分钟。

题面

题解

看着题解里一堆巨巨熟练地用着专业用语本萌新表示啥都看不懂啊……顺便\(orz\)余奶奶

我们先考虑给你一堆牌,如何判断能否胡牌

我们按花色大小排序,设\(dp_{0/1,i,j,k}\)表示是否有对子,考虑了前\(i\)种花色的牌,选了\(j\)个以\(i-1\)为开头的顺子(三个连续牌),\(k\)个以\(i\)为开头的顺子,此时能选的最大面子数。转移的话枚举以\(i+1\)为开头的顺子的个数,剩下的组成刻子(三个相同牌)就好了(加一个数字记为\(Trans\)

那么胡牌的条件有两个,\(\exists i,j,dp_{1,n,j,k}\geq 4\),或者记\(cnt\)为牌数\(\geq 2\)的花色数,\(cnt\geq 7\)

这个东西和\(i\)这一维关系不是很大,我们可以把它当成一个\(3\times 3\)的矩阵来转移。我们可以用一个结构体\(node\)来表示这个矩阵,并且为了维护\(dp_0\)\(dp_1\)我们需要开两个矩阵,并且记录\(cnt\),把这些所有都放到一个\(Mahjong\)结构体里。据说可行的\(Mahjong\)的状态只有\(3956\)

然后期望可以转化为\(ans=\sum\limits_{i=13}^{4n}p(i)\),其中\(p(i)\)表示摸了\(i\)张牌还不能胡的概率,所以转化为算摸了\(i\)张牌还不能胡的排列数

\(f_{i,j,k}\)表示我们考虑了前\(i\)种花色的牌,当前\(Mahjong\)的状态为\(j\),已经摸了\(k\)张牌的排列数是多少

转移的时候,我们枚举摸了花色\(i+1\)的张数\(z\),那么就可以转移到\(f_{i+1,Trans(j,z),k+z}\),乘上的系数是\((4 - org_{i + 1})^{\underline{z - org{i + 1}}} \binom{k + z - sum_{i + 1}}{z - org_{i + 1}}\)\(org_i\) 表示原有的 \(13\) 张牌中花色为 \(i\) 的有几张, \(sum\) 则是 \(org\) 的前缀和,这个式子的意思就是我们需要在没被选过的 \(4 - org_{i + 1}\) 张牌中选 \(z - org_{i + 1}\) 张的排列,并且插入到之前的排列中,但前 \(13\) 张牌的顺序是固定的。

最后\(p_i\)就等于摸了\(i\)张牌不赢的排列数减去摸\(i\)张牌的排列数

//minamoto#include
#define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
inline bool cmax(T&a,const T&b){return a
=P?x-=P:0;}inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){ R int res=1; for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0; return res;}int C[M][5],fac[5];void init(){ fp(i,0,M-1){ C[i][0]=1; fp(j,1,min(4,i))C[i][j]=add(C[i-1][j],C[i-1][j-1]); } fac[0]=1,fac[1]=1,fac[2]=2,fac[3]=6,fac[4]=24;}struct node{ int a[3][3]; node(){memset(a,-1,sizeof(a));} inline void init(){memset(a,-1,sizeof(a));} inline int* operator [](const int &x){return a[x];} bool operator <(node b)const{ fp(i,0,2)fp(j,0,2)if(a[i][j]!=b[i][j])return a[i][j]
=2),7); a.p[1]=Trans(a.p[1],b); if(b>=2)a.p[1]=Max(a.p[1],Trans(a.p[0],b-2)); a.p[0]=Trans(a.p[0],b); return a; } bool right(){ if(cnt==7)return true; fp(i,0,2)fp(j,0,2)if(p[1][i][j]==4)return true; return false; }}mahjong[M];map
mp;bool win[M];int n,tot,s[N],f[N][M][N<<2],trans[M][5];void dfs(Mahjong now){ if(mp.count(now))return; mahjong[++tot]=now,mp[now]=tot,win[tot]=now.right(); fp(i,0,4)dfs(Trans(now,i));}int main(){// freopen("testdata.in","r",stdin); init(),dfs(Mahjong()); fp(i,1,tot)fp(j,0,4)trans[i][j]=mp[Trans(mahjong[i],j)]; scanf("%d",&n); for(R int i=1,x;i<=13;++i)scanf("%d%*d",&x),++s[x]; f[0][1][0]=1; for(R int i=0,sum=0;i

转载于:https://www.cnblogs.com/bztMinamoto/p/10679698.html

你可能感兴趣的文章
福建泉州实行快捷通关模式 台轮“随到随检随走”
查看>>
BAT互联网公司,Java开发的最新招聘标准!
查看>>
「每天一道面试题」Semaphore的实现原理是什么?
查看>>
鸡西—哈尔滨—北京航线正式开通 促三地经贸交流
查看>>
山东检察机关适用认罪认罚从宽制度办理刑事案件3884件
查看>>
2018年,python的工资到底有多“吸金”?
查看>>
小米营销费用暴涨七成,但吴亦凡真的符合小米的气质吗?
查看>>
深度资讯|既要高抽成又要建生态,美团野心勃勃计划BC通吃
查看>>
百度、海淀区打造全球首个AI公园,北京人在家门口坐上无人车
查看>>
Servlet第六篇【Session介绍、API、生命周期、应用、与Cookie区别】
查看>>
Webpack2 的无脑友好错误提示工具
查看>>
Swift iOS : 如何一拖tableview到底的时候更新数据
查看>>
js千分位
查看>>
精读《Epitath 源码 - renderProps 新用法》
查看>>
基于后编译的国际化解决方案
查看>>
Spring Boot 揭秘与实战(二) 数据存储篇 - MongoDB
查看>>
开源计划之--Android绘图库--LogicCanvas
查看>>
[译] 在 Ubuntu 上安装 TensorFlow
查看>>
CCAI 2017 | 中国工程院院士李德毅:L3的挑战与量产
查看>>
Vue.js 第二天: 表单输入绑定
查看>>