自动搬运

查看原文

来自洛谷，原作者为

	ケロシ Blue Archive

搬运于2025-08-24 22:42:20，当前版本为作者最后更新于2023-01-05 17:43:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

题目给出了每一层掉回树根和爬高的概率，需求出爬到树顶的期望时间，很明显是一道概率 dp 题。
首先由于任何情况下甲壳虫都有可能掉回树根，所以正推较难，考虑逆推。
首先令 $f_i$ 为甲壳虫从 $i$ 到 $n$ 的期望时间，所以边界 $f_n=0$。
那么就可以推出状态转移方程 $f_i=p_{i+1} f_0+(1-p_{i+1})f_{i+1}+1$。
但是这个式子里有需要求的答案 $f_0$，所以考虑类似解方程的方法来推出 $f_0$。
$f_0=(1-p_1)f_1+p_1f_0+1$
$f_0=(1-p_1)[(1-p_2)f_2+p_2f_0+1]+p_1f_0+1$
$f_0=(1-p_1)(1-p_2)f_2+(1-p_2)p_1f_0+(1-p_1)+p_1f_0+1$
$f_0=(1-p_1)(1-p_2)f_2+f_0[(1-p_1)p_2+p_1]+[(1-p_1)+1]$
依次类推，可以把式子分成三项，那么最后变成这样。
$f_0=\prod_{i=1}^{n}(1-p_i) f_n+f_0p_i\sum_{i=1}^{n}\prod_{j=1}^{i-1}(1-p_j)+\sum_{i=1}^{n}\prod_{j=1}^{i}(1-p_j)$
设这三个系数为 $s1$,$s2$,$s3$。
$f_0=s1f_n+s2f_0+s3$
这三个系数都能 $O(n)$ 求出。
因为 $f_n=0$，所以就可以求出答案 $f_0=\frac{s3}{1-s2}$。

代码

代码部分需要注意的是有理数取模的问题，因为模数是质数，所以使用费马小定理求解。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int P=998244353;
int n,a[N],b[N];
int fp(int x,int y){ // 快速幂
    int res=1;
    for(;y;y>>=1){
        if(y&1) res=(1ll*res*x)%P;
        x=(1ll*x*x)%P;
    }
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
    int s1=1,s2=0,s3=0;
    for(int i=1;i<=n;i++){ 
        int p1=(1ll*a[i]*fp(b[i],P-2))%P; //费马小定理求出概率
        int p2=(1ll*(b[i]-a[i])*fp(b[i],P-2))%P;
        s3=(s3+s1)%P; // 计算系数
        s2=(s2+1ll*s1*p1)%P;
        s1=(1ll*s1*p2)%P;
    }
    printf("%d",(1ll*s3*fp(1-s2+P,P-2))%P);
    return 0;
}