2666 問題 D: 藍(lán)橋杯2022年第十三屆省賽真題-爬樹的甲殼蟲
時間限制: 1s
內(nèi)存限制: 256MB 提交: 2159 解決: 600
題目描述
有一只甲殼蟲想要爬上一顆高度為 n 的樹，它一開始位于樹根，高度為 0，當(dāng)它嘗試從高度 i ? 1 爬到高度為 i 的位置時有 Pi 的概率會掉回樹根，求它從樹根爬到樹頂時，經(jīng)過的時間的期望值是多少。
輸入
輸入第一行包含一個整數(shù) n 表示樹的高度。
接下來 n 行每行包含兩個整數(shù) xi , yi，用一個空格分隔，表示
。
輸出
輸出一行包含一個整數(shù)表示答案，答案是一個有理數(shù)，請輸出答案對質(zhì)數(shù) 998244353 取模的結(jié)果。其中有理數(shù)
對質(zhì)數(shù) P 取模的結(jié)果是整數(shù) c 滿足
0 ≤ c < P 且 c · b ≡ a (mod P)。
對質(zhì)數(shù) P 取模的結(jié)果是整數(shù) 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 。
比賽公告
|
第十三屆藍(lán)橋杯大賽軟件賽省賽 C/C++ 研究生組 |
|
|---|---|
|
C題 |
|
| D題 | |
| E題 | |
| F題 | |
| G題 | |
| H題 | |
| I題 | |
| J題 | |
注意事項：
1. 對于編程題目，要求選手給出的解答完全符合 GNU C/C++ 標(biāo)準(zhǔn)，不能使用諸如繪圖、Win32API、中斷調(diào)用、硬件操作或與操作系統(tǒng)相關(guān)的 API。
2. 代碼中允許使用 STL 類庫。
3. main 函數(shù)結(jié)束必須返回 0。
4. 所有依賴的函數(shù)必須明確地在源文件中 #include
5. 提交時，注意選擇使用C或C++語言。
比賽結(jié)束也可以提交，見題集2022年第十三屆藍(lán)橋杯大賽軟件類省賽C/C++研究生組真題