题解 | #Glass Bead Game# #ICPC# #昆明# #条件概率#

牛客32708G - ICPC2021 · 昆明 - Glass Bead Game

• https://ac.nowcoder.com/acm/contest/32708/G
• 来源：ICPC2021 · 昆明
• 知识点：条件概率
• 难度：蓝、铜牌题

题意

• 给出一个长度为 $n(n\le 100)n(n\backslash leq\; 100)$ 的排列，数字 $kk$ 被选中的概率是 $p_{k}p\_k$
• 刚开始序列是 $1,2,3,\dots n1,2,3,\backslash dots\; n$ 有序的。
• 现在随机选择一个元素（注意数字 $kk$ 被选中的概率是 $p_{k}p\_k$），将它移动到序列最前。假如选择的元素是从前往后第 $ii$ 个，那么花费是 $i-1i-1$。
• 现在进行了无穷次上述操作，问第无穷次操作代价的期望。

思路

• 能观察到，进行了无穷次操作以后，这 $n!n!$ 种排列，每一种排列的概率不均等。
• 因此，这个答案是错误的：$ans=\sum (p_i\times \frac{0+1+2+\dots (n-1)}{n})ans=\backslash sum\; (p\_i\backslash times\backslash frac\{0+1+2+\backslash dots\; (n-1)\}\{n\})$
• 考虑针对每个元素算贡献
• 对于标有数字 $kk$ 的元素，它被选中的概率是 $p_{k}p\_k$，假设排在它前面的元素数量的期望为 $xx$，那么它对答案的贡献为 $x\times p_{k}x\backslash times\; p\_k$
• 排在它前面的元素数量的期望 $xx$ 怎么计算？
• 考虑条件概率
• 对于标有数字 $ii$ 的元素，它前面的元素数量的期望 $x=\frac{p_1}{p_i+p_1}+\frac{p_2}{p_i+p_2}+\dots \frac{p_{i-1}}{p_i+p_{i-1}}+\frac{p_{i+1}}{p_i+p_{i+1}}+\dots \frac{p_n}{p_i+p_n}x\; =\; \backslash frac\{p\_1\}\{p\_i+p\_1\}+\backslash frac\{p\_2\}\{p\_i+p\_2\}+\backslash dots\; \backslash frac\{p\_\{i-1\}\}\{p\_i+p\_\{i-1\}\}+\backslash frac\{p\_\{i+1\}\}\{p\_i+p\_\{i+1\}\}+\backslash dots\; \backslash frac\{p\_n\}\{p\_i+p\_n\}$
• $ans=\sum x\times p_{i}ans=\backslash sum\; \{x\; \backslash times\; p\_i\}$

代码

double ans = 0;
for (int i=1; i<=n; i++)
{
    double sum = 0;
    for (int j=1; j<=n; j++)
    {
        if(i == j)
            continue;
        sum += pi[j] / (pi[i]+pi[j]);
    }
    ans += sum*pi[i];
}
printf("%.10lf\n",ans);