New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

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

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

题目描述

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

输入格式

输入第一行包含一个整数 n 表示树的高度。
接下来 n 行每行包含两个整数xi, yi，用一个空格分隔，表示Pi = xi/yi。
20%的测试数据：1≤n≤2，1≤xi<yi≤20;
50%的测试数据：1≤n≤500，1≤xi<yi<200；
100%的测试数据：1≤n≤100000，1≤xi<yi≤10^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