蓝桥杯第十三届省赛C/C++研究生组模拟_问题D

提交: 2156 解决: 600

题目描述

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

输入

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

接下来 n 行每行包含两个整数 x_i , yi，用一个空格分隔，表示。

输出

输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数 998244353 取模的结果。其中有理数

对质数 P 取模的结果是整数 c 满足 0 ≤ c < P 且 c · b ≡ a (mod P)。

样例输入

1
1 2

样例输出

提示

对于 20% 的评测用例，n ≤ 2，1 ≤ x_i < y_i ≤ 20 ；

对于 50% 的评测用例，n ≤ 500，1 ≤ x_i < y_i ≤ 200 ；

对于所有评测用例，1 ≤ n ≤ 100000，1 ≤ x_i < y_i ≤ 10⁹ 。

注意事项：

1. 对于编程题目，要求选手给出的解答完全符合 GNU C/C++ 标准，不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的 API。

2. 代码中允许使用 STL 类库。

3. main 函数结束必须返回 0。

4. 所有依赖的函数必须明确地在源文件中 #include

5. 提交时，注意选择使用C或C++语言。