Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届省赛真题-爬树的甲壳虫
题目 2666:

蓝桥杯2022年第十三届省赛真题-爬树的甲壳虫

时间限制: 2s 内存限制: 320MB 提交: 2155 解决: 600

题目描述

有一只甲壳虫想要爬上一颗高度为 n 的树,它一开始位于树根,高度为 0,当它尝试从高度 i − 1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根,求它从树根爬到树顶时,经过的时间的期望值是多少。

输入格式

输入第一行包含一个整数 n 表示树的高度。

接下来 n 行每行包含两个整数 xi , yi,用一个空格分隔,表示蓝桥杯2022年第十三届省赛真题爬树的甲壳虫1

输出格式

输出一行包含一个整数表示答案,答案是一个有理数,请输出答案对质数 998244353 取模的结果。其中有理数蓝桥杯2022年第十三届省赛真题爬树的甲壳虫2对质数 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

标签