P8774 [蓝桥杯 2022 省 A] 爬树的甲壳虫 题解

· · 题解

分析

题目给出了每一层掉回树根和爬高的概率，需求出爬到树顶的期望时间，很明显是一道概率 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;
}