Question

ICPC2021Kunming G Glass Bead Game

有 $n$ 个玻璃珠， $B_1,B_2,\cdots, B_n$ 每一步你可以选择一个 $B_i$ 移道第一个位置上，花费的代价为操作前 $B_i$ 前面的玻璃珠的个数。已知每一步选择玻璃珠 $B_i$ 的概率 $p_i$ ，问当 $m\rightarrow \infty$ 时，在第 $m$ 轮花费的期望代价是多少

Solution

记随机变量 $X$ 为第 $m$ 轮花费的代价

记随机变量 $X_{i,j}$ 为第 $m$ 轮选择 $B_j$ 且 $B_i$ 在 $B_j$ 前面为 $1$，其他情况为 $0$

有 $X=\sum_\limits{i\ne j} X_{i,j}$
$E(X)=\sum E(X_{i,j})=\sum P(X_{i,j}=1)$

设第 $m$ 轮时 $B_i$ 在 $B_j$ 前面的概率是 $f(m,i,j)$

有 $$f(m,i,j)=(1-p_j)f(m-1,i,j)+p_i(1-f(m-1,i,j))$$

两边 $m \rightarrow \infty$ 有

\[f(i,j)=(1-p_j)f(i,j)+p_i(1-f(i,j)) \]

解得

\[f(i,j)=\frac{p_i}{p_i+p_j} \]

则在第 $m$ 轮时，选择 $B_j$ 的概率是 $p_j$ 有

\[P(X_{i,j}=1)=\frac{p_ip_j}{p_i+p_j} \]

所以答案就是

\[\sum\limits_{i\ne j} \frac{p_i p_j}{p_i+p_j} \]

Code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;scanf("%d",&n);
    vector<double> p(n+1,0);
    for(int i=1;i<=n;i++) scanf("%lf",&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){
            sum+=p[j]/(p[i]+p[j]);
        }
        ans+=sum*p[i];
    }
    printf("%.10lf\n",ans);
}

526互联

ICPC2021Kunming G Glass Bead Game 题解

Question

Solution

Code