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

技术文档

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

题意：

一颗高度为 $n$ 的树，虫子一开始位于树根（高度为 $0$ ），当它尝试从高度 $i - 1$ 爬到高度为 $i$ 的位置时有 $P_i$ 的概率会掉回树根，同时需要花费 $1$ 的时间，求它从树根爬到树顶的期望时间。
$\\leq n \\leq 10^5,1 \\leq x_{i}<y_{i} \\leq 10^{9}$ 。

思路：

概率为 $p_i$ ,那么到达 $i + 1$ 的概率为 $1-p_{i+1}$ ,掉到 $0$ 的概率是 $p_{i+1}$ 。
设 $f_i$ 为 $i$ 到 $n$ 的期望,那么 $f_n=0$ 。
$f_i$ 的状态转移方程就是：
$f_i=1+(1-p_{i+1})f_{i+1}+p_{i+1}f_0$
表示 $f_i$ 到 $n$ 期望为：时间 $+$ 到 $i + 1$ 的期望 $+$ 掉到 $0$ 后 $f_0$ 的期望。

难道代码就是这样吗？并不是。我们观察式子发现求 $f_i$ 时,未知数有 $f_{i+1}$ 和 $f_0$ ,其中可以通过倒着求得出 $f_{i+1}$ ,但无法得出 $f_0$ 。
所以我们以 $n = 3$ 为例,展开前面的式子：
$f_0=1+(1-p_{1})f_{1}+p_{1}f_0$
$f_1=1+(1-p_{2})f_{2}+p_{2}f_0$
$f_2=1+(1-p_{3})f_{3}+p_{3}f_0$
然后把 $f_1$ 代入 $f_0$ ：
$f_0=1+(1-p_{1})[1+(1-p_{2})f_{2}+p_{2}f_0]+p_{1}f_0$
$f_0=1+(1-p_{1})+(1-p_{1})(1-p_{2})f_{2}+[p_{1}+(1-p_1)p_2]f_0$
这个时候可以找到一个规律：
$f_0=A+B+C$
$A=1+(1-p_1)+(1-p1)(1-p_2)+\\ldots+(1-p1)(1-p2)\\ldots(1-p_{n-1})$
$C=p_1+(1-p_1)p_2+\\ldots+(1-p1)(1-p_2)\\ldots(1-p_{n-1})p_n$
因为 $B$ 乘了 $f_n$ ,而 $f_n$ 为 $0$ ,所以 $B$ 可以不算。

还需要注意一点,因为题目要求一个分数除以一个素数,所以要用到逆元。

code

#include#include#includeusing namespace std;const int mod=998244353;const int N=100005;int n;long long a[N],b[N],A,C,p[N],p_1[N];long long ksm(long long x,long long p){long long res=1;while(p){if(p&1){res=res*x%mod;}x=x*x%mod;p>>=1;}return res;}int main(){scanf(\"%d\",&n);for(int i=1;i<=n;i++){scanf(\"%lld%lld\",&a[i],&b[i]);p[i]=a[i]*ksm(b[i],mod-2)%mod;p_1[i]=(b[i]-a[i])*ksm(b[i],mod-2)%mod;}A=1;long long k=1;for(int i=1;i<n;i++){A=(A+p_1[i]*k%mod)%mod;k=(p_1[i]*k)%mod;}k=1;for(int i=1;i<=n;i++){C=(C+p[i]*k%mod)%mod;k=(k*p_1[i])%mod;}C=(1-C+mod)%mod;long long ans=A*ksm(C,mod-2)%mod;printf(\"%lld\\n\",ans);return 0;}

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