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

· · 题解

先放个原题链接

题目分析

首先，题目主要是考察的是：

这个题我做对之后一直没有看到正序求解的题解，所以本人给出正序求解的解法。

先注意，题目中的 P_i 指的是在第 i 格高的时候摔下去的概率，而不是成功向上走的概率！

如图，我们先通过从 0 到 1 开始入手这道题目。我们令 dp[i] 为从 0 开始到达 i 的期望值。

首先我们的初始位置是在 (0,0)，目标是 1。我们第一次走的时候成功到 1 的概率是 1-P_1，到 (0,1) 的概率是 P_1，这时再到 1 的概率还是 1-P_1，到 (0,2) 的概率还是 P_1，以此类推。

我们都知道，初始的期望值为 0，也就是（dp[0]=0）。然后我们就可以得到如下这些式子。

\begin{aligned}dp[1]&=(1-P_1)+P_1\times (2(1-P_1)+P_1\times (3\times (1-P_1)+P_1\times (...)))\\&=(1-P_1)+2\times P_1\times (1-P_1)+3\times {P_1}^2\times (1-P_1)+4\times {P_1}^3\times (1-P_1)+...\end{aligned}

接下来错位相减：

dp[1]\times P_1=(1-P_1)\times P_1+2\times {P_1}^2\times (1-{P_1})+3\times {P_1}^3\times (1-P_1)+... dp[1]-dp[1]\times P_1=(1-P_1)+P_1\times (1-P_1)+{P_1}^2\times (1-P_1)+{P_1}^3\times (1-P_1)+... dp[1]\times (1-P_1)=(1-P_1)\times (1+P_1+{P_1}^2+{P_1}^3+...) dp[1]=1+P_1+{P_1}^2+{P_1}^3+{P_1}^4+...

由等比数列求和公式 1+x+x^2+x^3+...+x^n= \frac{x^{n+1}-1}{x-1} 得出 dp[1]=\frac{P_1^{n+1}-1}{P_1-1}。

因为 n 无限趋近于 + \infty ，所以 {P_1}^{n+1} 无限趋近于 0。由此可知 dp[1]=\frac{1}{1-P_1}。

这其实是一个结论，就是失败后没有回退的这种期望在该路径上的大小为 \frac{1}{P}（P 为成功的概率）。

其实上面主要是铺垫，接下来进入正题。

dp[i]=?

这里再插入一张图。

先解释一下，start 位置就是这个运算开始的位置，一开始我们的概率为 1，其中成功向上的概率为 (1-P_i)，摔落的概率为 P_i 。因为摔落的步数为 1，所以每摔落一次都要 +1。而我们从 0 重新回到 i 的期望为多少呢？也就是 dp[i-1] 了！再将摔落概率乘以 dp[i-1] ，就得到了以下这些式子。

\begin{aligned}dp[i]&=dp[i-1]+(1-P_i)+P_i\times (1+dp[i-1]+(1-P_i)+P_i\times (1+dp[i-1]+(1-P_i)+P_i\times (1+dp[i-1]+(1-P_i)+P_i\times (...))))\\&=dp[i-1]+(1-P_i)+P_i\times (1+dp[i-1]+(1-P_i))+{P_i}^2\times (1+dp[i-1]+(1-P_i))+{P_i}^3\times (1+dp[i-1]+(1-P_i))+{P_i}^4\times (...)\\&=dp[i-1]+(1-P_i)+P_i\times (1+dp[i-1]+(1-P_i))\times (1+{P_i}+{P_i}^2+{P_i}^3+...)\end{aligned}

再由上文提到的等比数列求和公式 1+x+x^2+x^3+...+x^n= \frac{x^{n+1}-1}{x-1}，得出：

dp[i]=dp[i-1]+(1-P_i)+P_i\times (1+dp[i-1]+(1-P_i))\times \frac{{P_i}^{n+1}-1}{P_i-1}

同理，当 n 无限趋近于 + \infty ，所以 {P_i}^{n+1} 无限趋近于 0。所以：

\begin{aligned}dp[i]&=dp[i-1]+(1-P_i)+\frac{P_i(1+dp[i-1]+(1-P_i))}{1-P_i}\\&=dp[i-1]+(1-P_i)+\frac{P_i+P_i\times dp[i-1] + P_i - {P_i}^2}{1-P_i}\\&=dp[i-1]+(1-P_i)+\frac{P_i\times dp[i-1] + 2\times P_i - {P_i}^2}{1-P_i}\\&=\frac{(1-P_i)\times dp[i-1] + (1-P_i)^2+P_i\times dp[i-1] + 2\times P_i - {P_i}^2}{1-P_i}\\&=\frac{dp[i-1] - P_i\times dp[i-1] +1 - 2\times P_i + {P_i}^2+ P_i\times dp[i-1] + 2\times P_i - {P_i}^2}{1-P_i}\\&=\frac{1+dp[i-1]}{1-P_i} \end{aligned}

将 P_i 替换成 \frac{x_i}{y_i}，得到：

\begin{aligned}dp[i]&=\frac{1+dp[i-1]}{1-\frac{x_i}{y_i}}\\&=\frac{1+dp[i-1]}{\frac{y_i-x_i}{y_i}}\\&=\frac{y_i\times (1+dp[i-1])}{y_i-x_i}\end{aligned}

终于，我们求出了转移方程。

剩下的问题主要是对分数取余。由于 Mod=998244353，是个素数，所以直接使用费马小定理和快速幂解决就行了，这里不再赘述。

Code Time

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100010,M=998244353;
int n;
ll dp[N];
ll ksm(ll x,ll y){//快速幂
    ll _ans=1;
    while(y){
        if(y&1){
            _ans*=x;
            _ans%=M;
        }
        x*=x;
        x%=M;
        y>>=1;
    }
    return _ans;
}
ll qy(ll x,ll y){//分数取余
    return x%M*ksm(y,M-2)%M;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        ll x,y;
        cin>>x>>y;
        dp[i]=qy((y*(1+dp[i-1]))%M,y-x);//转移方程
    }
    printf("%lld",dp[n]);
    return 0;
}