[蓝桥杯 2022 省 A] 爬树的甲壳虫

Luogu
IDLGP8774
Time1000ms
Memory128MB
DifficultyP4
动态规划 DP2022期望蓝桥杯省赛
有一只甲壳虫想要爬上一颗高度为 $n$ 的树,它一开始位于树根, 高度为 $0$,当它尝试从高度 $i-1$ 爬到高度为 $i$ 的位置时有 $P_{i}$ 的概率会掉回树根, 求它从树根爬到树顶时, 经过的时间的期望值是多少。 ## Input 输入第一行包含一个整数 $n$ 表示树的高度。 接下来 $n$ 行每行包含两个整数 $x_{i}, y_{i}$, 用一个空格分隔,表示 $P_{i}=\frac{x_{i}}{y_{i}}$ 。 ## Output 输出一行包含一个整数表示答案,答案是一个有理数,请输出答案对质数 $998244353$ 取模的结果。其中有理数 $\frac{a}{b}$ 对质数 $P$ 取模的结果是整数 $c$ 满足 $0 \leq c<P$ 且 $c \cdot b \equiv a\pmod P$ 。 [samples] ## Note 对于 $20 \%$ 的评测用例, $n \leq 2,1 \leq x_{i}<y_{i} \leq 20$; 对于 $50 \%$ 的评测用例, $n \leq 500,1 \leq x_{i}<y_{i} \leq 200$; 对于所有评测用例, $1 \leq n \leq 10^5,1 \leq x_{i}<y_{i} \leq 10^{9}$ 。 蓝桥杯 2022 省赛 A 组 E 题。
Samples
Input #1
1
1 2
Output #1
2
Input #2
3
1 2
3 5
7 11
Output #2
623902744
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2022 省 A] 爬树的甲壳虫",
    "description": {
      "content": "有一只甲壳虫想要爬上一颗高度为 $n$ 的树,它一开始位于树根, 高度为 $0$,当它尝试从高度 $i-1$ 爬到高度为 $i$ 的位置时有 $P_{i}$ 的概率会掉回树根, 求它从树根爬到树顶时, 经过的时间的期望值是多少。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8774"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一只甲壳虫想要爬上一颗高度为 $n$ 的树,它一开始位于树根, 高度为 $0$,当它尝试从高度 $i-1$ 爬到高度为 $i$ 的位置时有 $P_{i}$ 的概率会掉回树根, 求它从树根爬到树顶时, 经过的时间的期望值是多少。\n\n## Input\n\n输入第一行包含一个整数 $n$ 表示树的高度。\n\n接下来 $n$ 行每行包含两个整数 $x_{i}, y_{i}$, 用一个空格分隔,表示 $P_{...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments