Conjugate 题解【概率期望】【期望可加性】

作者: wjyyy 分类: 概率期望,解题报告 发布时间: 2018-10-24 19:29

点击量:33

 

    是一道比较有水平的期望题,和AGC028B很像。

 

题目描述

在不存在的\(\text{noip day3}\) ⾥,小\(\text w\)见到了⼀堆堆的谜题。

比如这题为什么会叫共轭?

他并不知道答案。

有\(n\)堆谜题,每堆有\(a_i\)个,小\(\text w\)每次从剩下的谜题中随机选择⼀个,然后把所在的那⼀堆谜题全部丢掉。

小\(\text w\)期望多少次后丢掉第⼀堆?

输入格式

一行一个整数\(n\)。

一行\(n\)个整数,表示\(a_i\)。

输出格式

⼀⾏⼀个数表示期望,误差不得超过\(10^{-6}\)。

输入输出样例

输入样例1:

2
1 1

输出样例1:

1.5

数据规模与约定

对于\(20\%\)的数据,\(n\le 10\)。

对于\(40\%\)的数据,\(n\le 1000\)。

对于另外\(20\%\)的数据,\(a_i=1\)。

对于\(100\%\)的数据,\(n\le 10^5,1\le a_i\le 10^9\)。

题解:

    首先看到这个题要读懂题意:每次随机选一组删掉,概率与\(a_i\)有关,当删掉第\(1\)组时游戏结束。

    这个随机其实只是对原来的操作加上了概率的影响,实际上操作顺序还是排列。因此对于这题的暴力,我们可以深搜出全排列并把概率带进去,搜到\(1\)时将答案加上概率×次数即可。

    这一过程是不会向\(1\)的后面扩展的,因此每次找到\(1\)就会停下来。此时可以发现,在每个排列中,只有在\(1\)之前的元素做出了贡献,而这一排列,设为\(\{p_1,p_2,p_3,\dots ,p_k,1,\dots \}\),则贡献为\[\frac{a_{p_1}}{sum}\times \frac{a_{p_2}}{sum-a_{p_1}}\times \frac{a_{p_3}}{sum-a_{p_1}-a_{p_2}}\times \dots \frac{a_1}{sum-a_{p_1}-a_{p_2}-\dots -a_{p_k}}\]

    这样的话会非常难算。实际上一个数\(k\)做出贡献,当且仅当出现它在\(1\)的前面。此时可以不用考虑其他元素,单独考虑这两个,那么在\(1\)和\(k\)两个集合中,如果第一个被选出的是\(k\)集合中的元素,那么它就会做出贡献,这一情况出现的概率是\(\frac{a_k}{a_k+a_1}\)。也就是保证了\(k\)是这\(a_k+a_1\)个元素中第一个被选出来的元素。

    因此我们单独考虑每个元素,根据期望可加性,把每个元素的概率\(\frac{a_i}{a_i+1}\)乘上次数\(1\)(即贡献)加起来再\(+1\)就是答案。这里前一个\(1\)表示每次操作次数增加\(1\),那么这次操作的期望贡献就是其概率(只是乘了个单位\(1\));后面一个\(1\)就是最后一次操作选择且一定选择了\(1\),这个不用分开计算,因为它是一定会出现的。

    编程复杂度极低,时间复杂度为\(O(n)\)。

Code:

#include<cstdio>
#include<cstring>
int main()
{
    int n,a1,u;
    scanf("%d",&n);
    double ans=0.0;
    scanf("%d",&a1);
    for(int i=2;i<=n;++i)
    {
        scanf("%d",&u);
        ans=ans+(double)u/(a1+u);
    }
    printf("%.8lf\n",ans+1);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */