本文主要是介绍【数学】第十三届蓝桥杯省赛C++ A组/研究生组《爬树的甲壳虫》（C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
有一只甲壳虫想要爬上一棵高度为 n 的树，它一开始位于树根，高度为 0，当它尝试从高度 i−1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。
【输入格式】
输入第一行包含一个整数 n 表示树的高度。
接下来 n 行每行包含两个整数 xi,yi，用一个空格分隔，表示 Pi=xi / yi。
【输出格式】
输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数 998244353 取模的结果。
其中有理数 a / b 对质数 P 取模的结果是整数 c 满足 0≤c<P 且 c⋅b≡a(modP)。
【数据范围】
对于 20% 的评测用例，n≤2，1≤xi<yi≤20；
对于 50% 的评测用例，n≤500，1≤xi<yi≤200；
对于所有评测用例，1≤n≤100000，1≤xi<yi≤10的9次方，为了保证不出现无解的情况，额外增加限制条件 yi−xi≠998244353（如不增加此条件，则可能出现无解情况，此为比赛原题考虑不周）。
【输入样例1】
1
2
【输出样例1】
2
【输入样例2】
3
1 2
3 5
7 11
【输出样例2】
623902744
【代码】
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int P = 998244353;int n;LL qmi(int a, int b)
{LL res = 1;while (b){if (b & 1) res = res * a % P;a = (LL)a * a % P;b >>= 1;}return res;
}int main()
{scanf("%d", &n);int res = 0;while (n -- ){int x, y;scanf("%d%d", &x, &y);res = (res + 1ll) * y % P * qmi(y - x, P - 2) % P;}printf("%d\n", res);return 0;
}这篇关于【数学】第十三届蓝桥杯省赛C++ A组/研究生组《爬树的甲壳虫》（C++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
