标签：int 题解 sum Glass Game ICPC2021Kunming 玻璃珠 Bead

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);
}

标签：int,题解,sum,Glass,Game,ICPC2021Kunming,玻璃珠,Bead
From： https://www.cnblogs.com/martian148/p/17933795.html