洛谷题目： P8774 [蓝桥杯 2022 省 A] 爬树的甲壳虫 题解 （本题较简）

题目传送门：

P8774 [蓝桥杯 2022 省 A] 爬树的甲壳虫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

前言：

这是一道关于概率和期望的动态规划问题，解题的核心思路是通过建立状态转移方程来计算甲壳虫从树根爬到树顶所需时间的期望值。题目还是非常的简单。

#思路：

        1、问题抽象与定义状态：

                我们设树的高度为  ，甲壳虫从高度  爬到高度   时掉回树根的概率为     。我们定义    表示甲壳虫从树根（高度为0时）爬到高度为  的位置所需时间的期望值。我们的目标是求出     。

        2、分析状态转移过程：

                考虑到甲壳虫从高度  爬到高度  的过程，存在两种可能的情况。

                1.1、成功爬到高度  ：

                        甲壳虫以     的概率从高度  成功爬到高度  。在这种情况下，它首先需要花费   的时间从树根爬到高度  爬到高度  的过程中掉回树根。正在这种情况下，它先花费   的时间从树根爬到高度  ， 接着花费 1 个单位时间尝试从高度 爬到高度  但失败掉回树根，最后还需要花费   的时间重新从树根爬到搞  。所以这种情况下总共花费的时间为        。

        3、建立状态转移方程：

                1.1、根据期望的定义，期望值是所有可能结果的概率乘以对应结果的和。 对于   ，可以列出如下方程：

        

                1.2、对方程进行化简：

                        首先展开式子：

                     

                        然后合并同类项：

                        

                        

                        接着我们移项就得到：

                        

                        提取公因式：

                        

                        最后求解   ：

                        

        4、处理分数取模问题：

                1.1、由于题目要求结果对质数 MOD=998244353取模，而状态转移方程中涉及到分数的计算，所以需要将分数转化为整数在模意义下进行计算。

                1.2、根据费马小定理，对于质数 MOD 与 MOD 互质的整数  ，有                        ​​​​​​​           （mod MOD），那么  （mod MOD），也就是  （mod MOD）。

                1.3、因此我们在计算    时，  可以转换为“

                          （mod MOD）。 这里使用快速幂算法来计算   ，时间复杂度为 。

        5、初始化和最终结果：

                1.1、初始化     ，因为甲壳虫一开始就在树根，高度为0，所需时间的期望值为0.

                1.2、然后按照状态转移方程依次计算   ，最终  就是甲壳虫从树根爬到输定所需时间的期望值，将其对 MOD取模后输出。

##代码：

#include <bits/stdc++.h>
using namespace std;
const int M = 998244353;
long long q(long long a, long long b) {long long r = 1;while (b) {if (b & 1) {r = r * a % M;}a = a * a % M;b >>= 1;}return r;
}
long long m(long long a, long long b) {return a * q(b, M - 2) % M;
}
int main() {int n;cin >> n;vector<int> x(n + 1), y(n + 1);vector<long long> dp(n + 1, 0);for (int i = 1; i <= n; ++i) {cin >> x[i] >> y[i];}for (int i = 1; i <= n; ++i) {long long p = m(x[i], y[i]);dp[i] = (dp[i - 1] + 1) * q(1 - p + M, M - 2) % M;}cout << dp[n] << endl;return 0;
}