数学期望dp + 推导 + 快速幂 $O(nlogn)$

$令X(i)表示从高度为i的位置爬到树顶的事件，即最终答案为E(X(0))\\ X(i)要想到终点，那么它的下一个X(i + 1)要到终点，或者从X(0)到终点两种情况\\ 则X(i) = ((1 - p_i) \cdot (X(i + 1) + 1) + p_i \cdot (X(0) + 1) \\ +1才是i+1的时间\\ 对应的期望为\\ E(i) = (1 - p_i) E(i + 1) + p_i E(0) + 1 - p_i + p_i \\ 令E(i) \Leftrightarrow f(i)\\ f(i) = (1 - p_i) f(i + 1) - (1 - p_i) f(0) + f(0) + 1 \\ f(0) - f(i) = (1 - p_i) (f(0) - f(i + 1)) - 1 \\ 令g(i) = f(0) - f(n)可以得到递推式\\ g(i + 1) = \dfrac{g(i) + 1}{1 - p_1}\\ 又因为g(n) = f(0) - f(n)\\ 因为f(n) = 0所以g(n) = f(0)\\ 因此求出g(n)即解的答案\\ $

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int mod = 998244353, N = 100010;

int g[N];
int n;
int qmi(int a, int b){
    int res = 1;
    while (b){
        if (b & 1) res = (LL)res * a % mod;
        a = (LL) a * a % mod;
        b >>= 1;
    }
    return res;
}

int main(){
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++){
        int x, y;
        scanf("%d%d", &x, &y);
        g[i] = (g[i - 1] + 1ll) * y % mod * qmi(y - x, mod - 2) % mod;
    }

    printf("%d\n", g[n]);
    return 0;
}