qidao123.com技术社区-IT企服评测·应用市场
标题:
洛谷标题： P8774 [蓝桥杯 2022 省 A] 爬树的甲壳虫 题解 （本题较简）
[打印本页]
作者:
麻花痒
时间:
2025-4-9 19:03
标题:
洛谷标题： P8774 [蓝桥杯 2022 省 A] 爬树的甲壳虫 题解 （本题较简）
标题传送门：
P8774 [蓝桥杯 2022 省 A] 爬树的甲壳虫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
前言：
这是一道关于概率和期望的动态规划问题，解题的核心思路是通过建立状态转移方程来计算甲壳虫从树根爬到树顶所需时间的期望值。标题还是非常的简朴。
#思路：
1、问题抽象与定义状态：
我们设树的高度为
，甲壳虫从高度
爬到高度
时掉回树根的概率为
。我们定义
表示甲壳虫从树根（高度为0时）爬到高度为
的位置所需时间的期望值。我们的目标是求出
。
2、分析状态转移过程：
考虑到甲壳虫从高度
爬到高度
的过程，存在两种可能的情况。
1.1、成功爬到高度
：
甲壳虫以
的概率从高度
成功爬到高度
。在这种情况下，它起首需要花费
的时间从树根爬到高度
爬到高度
的过程中掉回树根。正在这种情况下，它先花费
的时间从树根爬到高度
， 接着花费 1 个单位时间实验从高度
爬到高度
但失败掉回树根，最后还需要花费
的时间重新从树根爬到搞
。所以这种情况下统共花费的时间为
。
3、建立状态转移方程：
1.1、根据期望的定义，期望值是所有可能结果的概率乘以对应结果的和。 对于
，可以列出如下方程
：
1.2、对方程举行化简：
起首睁开式子：
然后合并同类项：
[img]https://latex.csdn.net/eq?dp%5Bi%5D%3D%281-P_%7Bi%7D&plus
_%7Bi%7D%29dp%5Bi-1%5D+%281-P_%7Bi%7D&plus
_%7Bi%7D%29&plus
_%7Bi%7Ddp%5Bi%5D[/img]
[img]https://latex.csdn.net/eq?dp%5Bi%5D%3Ddp%5Bi-1%5D+1&plus
_%7Bi%7Ddp%5Bi%5D[/img]
接着我们移项就得到：
提取公因式：
最后求解
：
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;
}
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)
Powered by Discuz! X3.4
_%7Bi%7D%29dp%5Bi-1%5D+%281-P_%7Bi%7D&plus_%7Bi%7D%29&plus_%7Bi%7Ddp%5Bi%5D[/img]_%7Bi%7Ddp%5Bi%5D[/img]