RainAir
My OI Blog
RainAir
ZROI1121 小E和小F strikes again

题目

2019 十一权限

题解

每次小 E 肯定会选择获胜概率最大的那个颜色,我们首先考虑如何算出这个概率。
首先题目里的排列形式是没有意义的,可以通过组合数来变成选取一些数。

首先 如果对于颜色 $c$ ,它总共有 $a_c$ 个,这次小 E 手里这个颜色的数的的数量为 $b_c$,令 $N = \sum a_i$,那么获胜概率应该就是:
$$\frac{\sum_{i} \binom {a_c – b_c}{i} \binom {N-(a_c-b_c)-x}{y-i}[b_c-i \geq z]}{\binom {N – x} y}$$
然后发现不同的概率的数目是 $O(N)$ 的,所以我们首先把所有的概率都求出来,然后我们枚举一个最大值,然后我们算出来所有情况中满足最大值是这个数的情况的概率,乘上获胜概率就是这种情况的获胜概率了。
假设我们已经知道了第 $i$ 个颜色选择了 $b_i$ 个,那么利用简单的组合计数可以得到概率:
$$\frac{\prod_i \binom {a_i}{b_i}}{\binom N x}$$
这个概率是可以用简单的 dp 计算出来的,然后乘起来就好了。
代码:

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/833
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

ZROI1121 小E和小F strikes again
题目 2019 十一权限 题解 每次小 E 肯定会选择获胜概率最大的那个颜色,我们首先考虑如何算出这个概率。 首先题目里的排列形式是没有意义的,可以通过组合数来变成选取一些数。 首先 …
扫描二维码继续阅读
2019-10-01
标签
近期评论