2666 問(wèn)題 D: 藍(lán)橋杯2022年第十三屆省賽真題-爬樹(shù)的甲殼蟲(chóng)
時(shí)間限制: 1s
內(nèi)存限制: 256MB 提交: 2159 解決: 600
題目描述
有一只甲殼蟲(chóng)想要爬上一顆高度為 n 的樹(shù)，它一開(kāi)始位于樹(shù)根，高度為 0，當(dāng)它嘗試從高度 i ? 1 爬到高度為 i 的位置時(shí)有 Pi 的概率會(huì)掉回樹(shù)根，求它從樹(shù)根爬到樹(shù)頂時(shí)，經(jīng)過(guò)的時(shí)間的期望值是多少。
輸入
輸入第一行包含一個(gè)整數(shù) n 表示樹(shù)的高度。
接下來(lái) n 行每行包含兩個(gè)整數(shù) xi , yi，用一個(gè)空格分隔，表示
。
輸出
輸出一行包含一個(gè)整數(shù)表示答案，答案是一個(gè)有理數(shù)，請(qǐng)輸出答案對(duì)質(zhì)數(shù) 998244353 取模的結(jié)果。其中有理數(shù)
對(duì)質(zhì)數(shù) P 取模的結(jié)果是整數(shù) c 滿(mǎn)足
0 ≤ c < P 且 c · b ≡ a (mod P)。
對(duì)質(zhì)數(shù) P 取模的結(jié)果是整數(shù) c 滿(mǎn)足
0 ≤ c < P 且 c · b ≡ a (mod P)。 樣例輸入
1 1 2
樣例輸出
2
提示
對(duì)于 20% 的評(píng)測(cè)用例，n ≤ 2，1 ≤ xi < yi ≤ 20 ；
對(duì)于 50% 的評(píng)測(cè)用例，n ≤ 500，1 ≤ xi < yi ≤ 200 ；
對(duì)于所有評(píng)測(cè)用例，1 ≤ n ≤ 100000，1 ≤ xi < yi ≤ 109 。
比賽公告
| 第十三屆藍(lán)橋杯大賽軟件賽省賽 Java 研究生組 | |
|---|---|
| C題 | |
| D題 | |
| E題 | |
| F題 | |
| G題 | |
| H題 | |
| I題 | |
| J題 | |
注意事項(xiàng)：
1. 不要使用 package 語(yǔ)句。
2. 選手代碼的主類(lèi)名必須為：Main，否則會(huì)被判為無(wú)效代碼。
3. 如果程序中引用了類(lèi)庫(kù)，在提交時(shí)必須將 import 語(yǔ)句與程序的其他部分同時(shí)提交。
4. 只允許使用 Java 自帶的類(lèi)庫(kù)。
5. 提交時(shí)，注意選擇使用Java語(yǔ)言。
本比賽結(jié)束依舊可以訓(xùn)練，見(jiàn)題集2022年第十三屆藍(lán)橋杯大賽軟件類(lèi)省賽Java研究生組真題