loopers期望题目感悟-期望的线性性

”我想永远当你最珍贵的宝物..……“
米娅有 n 个寻宝的地区,在第 i 个地区寻宝可以带来 (a_i) 的快乐值,每次米娅会随机选择一个还没有的搜寻过的地区进行寻宝,搜寻第 个地区( 还没有搜寻过)的概率为。

[frac{a_i}{sum_{j未搜寻}} ]

搜寻后会得到 (a_i) 的快乐值
由于某种原因,米娅搜寻了一号地区后就会停止,米娅想知道她可以获得的快乐值的期望由于miya只在一天不断轮回,所以米娅只想知道这个数在 意义下的值。

所以我们可以比较容易(屁)发现对于每个i有i必须在1前选择才能完成。

所以我们可以根据期望的线性性,eg: CF280C Game on Tree

所以我们考虑一整个序列,一个i有效当且仅当它在 (a_1) 之前的序列中出现,所以我们可以考虑仅仅这两个的位置关系:

即有 (frac{a_i}{a_1+a_i}) 的期望对于每个i,线性逆元累加就可以

棘手问题:处理逆元:

我们求出前缀积 (h_i) 函数和后缀积 "(t_i)" 函数并且求出 $ prod _{a_i+a1}^n$ 的逆元,然后乘上前后缀就可以愉快解决了,效仿 $ O(n)$ 求 (1 sim i) 阶乘的逆元。

代码加载失败
内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/jcyf1987/p/15422622.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!