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

点击量：208

    是一道比较有水平的期望题，和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;
}