2025: [蓝桥杯2022初赛] 爬树的甲壳虫

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:427 通过:242

题目描述

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

输入格式

输入第一行包含一个整数 n 表示树的高度。
接下来 n 行每行包含两个整数xi, yi,用一个空格分隔,表示Pi = xi/yi
20%的测试数据:1n≤2,1≤xi<yi≤20;
50%的测试数据:1n≤500,1≤xi<yi<200;
100%的测试数据:1n100000,1≤xi<yi10^9。

输出格式

输出一行包含一个整数表示答案,答案是一个有理数,请输出答案对质数 998244353 取模的结果。
其中有理数 a/b 对质数 P 取模的结果是整数 c 满足0 ≤ c < P 且c · b  a (mod P)。

输入样例 复制

样例1:
1
1 2

样例2:
3
1 2
3 5
7 11

输出样例 复制

样例1:
2

样例2:
623902744