[Codeforces 1265E]Beautiful Mirrors

Description

一共有 \(n\) 个关卡，你初始在第一个关卡。通过第 \(i\) 个关卡的概率为 \(p_i\)。每一轮你可以挑战一个关卡。若通过第 \(i\) 个关卡，则进入第 \(i+1\) 个关卡，否则重新回到第 \(1\) 个关卡。通过第 \(n\) 个关卡则算成功。问期望多少轮游戏才能成功。

\(1\leq n\leq 2\cdot 10^5\)

Solution

设从第 \(i\) 个关卡通关的期望为 \(E_i\)。显然
\[
E_i=p_i(E_{i+1}+1)+(1-p_i)(E_1+1)
\]

特别地，\(E_{n+1}=0\)，且答案为 \(E_1\)。

那么有
\[
E_1=p_1(E_2+1)+(1-p_1)(E_1+1)\Rightarrow E_1=\frac{1}{p_1}+E_2
\]

同理将上述式子代入
\[
E_2=p_2(E_3+1)+(1-p_2)(E_2+1)\Rightarrow E_1=\frac{1+\frac{1}{p_1}}{p_2}+E_3
\]

继续推导可以发现答案为
\[
E_1=\frac{1+\frac{1+\frac{1+\cdots}{p_{n-2}}}{p_{n-1}}}{p_n}
\]

Code

#include <bits/stdc++.h>

using namespace std;

const int yzh = 998244353;

int quick_pow(int a, int b) {

    int ans = 1;

    while (b) {

        if (b&1) ans = 1ll*ans*a%yzh;

        b >>= 1, a = 1ll*a*a%yzh;

    }

    return ans;

}

int main() {

    int ans = 0, p, n;

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {

        scanf("%d", &p);

        ans = (ans+1)%yzh;

        ans = 1ll*ans*100%yzh*quick_pow(p, yzh-2)%yzh;

    }

    printf("%d\n", ans);

    return 0;

}

巴特西

[Codeforces 1265E]Beautiful Mirrors

Description

Solution

Code

最新文章

热门文章