2024寒假每日一题全部题解传送门>>

又是疯狂推公式的一题…接下来开推吧。

甲壳虫从高度$i-1$的位置爬到高度$i$的位置，对于这一个过程中甲壳虫最少需要一次爬到高度$i$的位置，最多要爬无穷次才能到高度$i$的位置。甲壳虫不能从$i-1$爬到$i$的位置的概率为$P_k$，则能到达高度$i$的位置的概率为$(1-P_k)$，那么这一个过程中的期望分布如下（假设甲壳虫是从高度$0$爬到高度$1$的位置，$i$为爬的次数）：
$i=1$，$P_i=(1-P_1)$。
$i=2$，$P_i=(1-P_1)P_1$。
$i=3$，$P_i=(1-P_1)P_1^2$。
…
$i=n$，$P_i=(1-P_1)P_1^{n-1}$。
由题可知，$n\rightarrow\infty$，则到达高度$1$处的数学期望为：$(1-P_1)\sum\limits_{i=1}^{\infty}iP_1^{i-1}$。而$\sum\limits_{i=1}^{\infty}iP_1^{i-1}=(\sum\limits_{i=1}^{\infty}P_1^i)’ $。众所周知，将$\sum\limits_{i=1}^{\infty}x^i$写成和函数的形式，即$\sum\limits_{i=1}^{\infty}x^i=\frac{x}{1-x}$，故$\sum\limits_{i=1}^{\infty}iP_1^{i-1}=(\sum\limits_{i=1}^{\infty}P_1^i)’$$=(\frac{P_1 }{1-P_1})’=\frac{1}{(1-P_1)^2}$。故$E_1=$$(1-P_1)\sum\limits_{i=1}^{\infty}iP_1^{i-1}=(1-P_1)\frac{1}{(1-P_1)^2}=\frac{1}{1-P_1}=\frac{y_1}{y_1-x_1}$。

接下来来分析一般情况（即甲壳虫从高度$i-1$的位置爬到高度$i$的位置），首先要从高度$0$爬到高度$i-1$的位置，这一过程的期望为$E_{i-1}$，那么从高度$i-1$的位置爬到高度$i$的位置的期望分布为：
$i=1$，$P_i=E_{i-1}(1-P_i)+(1-P_i)=(E_{i-1}+1)(1-P_i)$。
$i=2$，$P_i=E_{i-1}(1-P_i)P_i+(1-P_i)P_i=(E_{i-1}+1)(1-P_i)P_i$。
$i=3$，$P_i=E_{i-1}(1-P_i)P_i^2+(1-P_i)P_i^2=(E_{i-1}+1)(1-P_i)P_i^2$。
…
$i=n$，$P_i=E_{i-1}(1-P_i)P_i^{n-1}+(1-P_i)P_i^{n-1}=(E_{i-1}+1)(1-P_i)P_i^{n-1}$。

由题可知，$n\rightarrow\infty$，则到达高度$i$处的数学期望为：$(1-P_i)(E_{i-1}+1)\sum\limits_{i=1}^{\infty}iP_i^{i-1}$。接下来化简同上，最后得到推导公式：$E_i=(E_{i-1}+1)(1-P_i)\sum\limits_{i=1}^{\infty}iP_i^{i-1}=(E_{i-1}+1)(1-P_i)\frac{1}{(1-P_i)^2}=\frac{E_{i-1}+1}{1-P_i}=$$\frac{y_i(E_{i-1}+1)}{y_i-x_i}$。

故设$f[i]$为从高度$i-1$到高度$i$处的期望，那么$f[i]=\frac{y_i(f[i-1]+1)}{y_i-x_i}$，故到达位置$n$处的期望即为$f[n]$。

C++代码：

#include<iostream>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e5 + 10, MOD = 998244353;
PII P[N];
int f[N];
int n;

int qmi(int a, int b) // 快速幂求逆元
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = (LL)res * a % MOD;
        b >>= 1;
        a = (LL)a * a % MOD;
    }

    return res;
}

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

    for(int i = 1; i <= n; i ++) scanf("%d%d", &P[i].x, &P[i].y);

    for(int i = 1; i <= n; i ++)
        f[i] = ((LL)f[i - 1] + 1) * P[i].y % MOD * qmi(P[i].y - P[i].x, MOD - 2) % MOD;

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