第十三届蓝桥杯省赛A组题解传送门

题目大意

有一只甲壳虫想要爬上一颗高度为$n$的树，它一开始位于树根，高度为$0$，当它尝试从高度$i−1$爬到高度为$i$的位置时有$P_i$的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少

解题思路

不懂数学期望的话看看定义就能懂，这是离散型的随机变量，微积分那一块不用管
数学期望定义
记$E_i$为甲壳虫从高度为$i$的地方爬到树顶的时间期望
那么根据题意，能列出下面两个式子
$(1)\ E_n=0$
$(2)\ E_i=1+P_{i+1}E_0+(1-P_{i+1})E_{i+1}$
我们可以由此递推出$E_0$的表达式，即从树根爬到树顶的时间期望
推导过程如下($Markdown$语法太长了就不打了)：

推导到这里，题目完成了一半
现在我们知道了$E_0$表达式和每个$P_i$，思考怎么快速求出来$E_0$
$E_0$是一个和式，记$s_i$为和式的第$i$项，可以发现每个$s_i$是可以由$s_{i-1}$快速得到的

最后，这题还考察了除法取余，需要乘法逆元
因为它模数给的是$998244353$，基本上就是明示我们直接用费马小定理+快速幂求逆元即可

实际代码并不难，能推出$E_0$表达式基本就成功了

具体代码

#include <bits/stdc++.h>
typedef long long LL;
const int N = 1e5 + 10;
const int INF = 1e9 + 10;
const int MOD = 998244353;
int a[N], b[N];
int n;
int qmi(int a, int k, int p)
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1)
            res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin >> n;
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i] >> b[i];
    int res = 0;
    LL t = 1;
    for (int i = 1; i <= n; ++i) //并不需要真的开个s数组，直接维护一个t就行
    {
        t = t * b[n - i + 1] % MOD;
        t = t * qmi(b[n - i + 1] - a[n - i + 1], MOD - 2, MOD) % MOD;
        res = (res + t) % MOD;
    }
    std::cout << res << '\n';
    return 0;
}