题解 | F

小红的删字符

https://ac.nowcoder.com/acm/contest/73760/A

alt alt 含义:此时A有x1个1牌,y1个2牌,B有x2个1牌,y2个2牌,这种状态能再打几局

然后就是套路题了

再考虑转移,分4种情况讨论 ,记res为本个dfs的答案,初始值设1(后面细说为什么)

  • 无法再进行下去,即两者都只有一样数值的卡牌或者两个人都没有卡牌了,返回0

  • alt alt

  • alt alt

  • 最后是两种均出一样卡牌的情况,我们注意到此时dfs后由于没有牌会减少,所以参数是不变的,取到这种情况的概率为p3=1-p1-p2,我们设最终本次dfs的结果为f,则有alt

所以每次dfs只需要模拟上面的过程就行了,然后需要把除法换成逆元,记得把负数换成正数就可以了

最后解释一下为什么res初始设1: 事实上,考虑状态的含义,res应该是0,区别在转移上,当res初始设0时,正确的方程应该是:alt 而我们知道把1的所有系数提出来,和必定为1(因为包含了所有情况),所以res设1实际上只是提前了一步,这样的过程是基本通用的

对不起,牛客的文本编辑器好难用QwQ,委屈一下将就着看吧 最后给一下code: ll是long long(龙龙)

alt

全部评论
好棒好喜欢
点赞
送花
回复
分享
发布于 02-05 01:13 江苏

相关推荐

10 收藏 评论
分享
牛客网
牛客企业服务