2666 问题 D: 蓝桥杯2022年第十三届省赛真题-爬树的甲壳虫
时间限制: 1s
内存限制: 256MB 提交: 2106 解决: 585
题目描述
有一只甲壳虫想要爬上一颗高度为 n 的树，它一开始位于树根，高度为 0，当它尝试从高度 i − 1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。
输入
输入第一行包含一个整数 n 表示树的高度。
接下来 n 行每行包含两个整数 xi , yi，用一个空格分隔，表示
。
输出
输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数 998244353 取模的结果。其中有理数
对质数 P 取模的结果是整数 c 满足
0 ≤ c < P 且 c · b ≡ a (mod P)。
对质数 P 取模的结果是整数 c 满足
0 ≤ c < P 且 c · b ≡ a (mod P)。 样例输入
1 1 2
样例输出
2
提示
对于 20% 的评测用例，n ≤ 2，1 ≤ xi < yi ≤ 20 ；
对于 50% 的评测用例，n ≤ 500，1 ≤ xi < yi ≤ 200 ；
对于所有评测用例，1 ≤ n ≤ 100000，1 ≤ xi < yi ≤ 109 。