AcWing:4646. 爬树的甲壳虫
描述:
有一只甲壳虫想要爬上一颗高度为 n 的树，它一开始位于树根，高度为 0，当它尝试从高度 i−1爬到高度为 i 的位置时有 Pi 的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。
输入格式
输入第一行包含一个整数 n 表示树的高度。
接下来 n 行每行包含两个整数 xi,yi，用一个空格分隔，表示 Pi=xi/yi。
输出格式
输出一行包含一个整数表示答案，答案是一个有理数，请输出答案对质数 998244353 取模的结果。
其中有理数 ab 对质数 P 取模的结果是整数 c 满足 0≤c<P 且 c⋅b≡a(modP)。
数据范围
对于 20% 的评测用例，n≤2，1≤xi<yi≤20；
对于 50% 的评测用例，n≤500，1≤xi<yi≤200；
对于所有评测用例，1≤n≤100000，1≤xi<yi≤109。
输入样例1：
1
1 2
输出样例1：
2
输入样例2：
3
1 2
3 5
7 11
输出样例2：
623902744假设当高度为k时，从树根爬到k所需要的期望时间是f(k)
从f(k−1)出发，爬到高度为k有两种方式：
1.直接从k−1的位置多爬一格不掉下去；
2.从k−1个的位置多爬一个的时候先掉下去了，再从底部爬完k。
得出推导式
f(k)=(f(k−1)+1)(1−pk)+(f(k−1)+1+f(k))pk,
化简上式
f(k)=f(k−1)+1/(1−pk)
代入 pk=xk/yk
f(k)=yk(f(k−1)+1)/yk−xk
直接用费马小定理+快速幂求逆元
以下是AC代码:
#include <iostream>
#include <cstring>
#include <algorithm>/* 定义 */
using namespace std;
typedef long long LL;
const int MOD = 998244353;
int n , ans = 0;/* 快速幂模版 */
int qsm(int a , int b)
{int res = 1 % MOD;for(; b ; b >>= 1){if(b & 1) res = 1ll * res * a % MOD;a = 1ll * a * a % MOD;}return res;
}int main()
{/* 读入 */cin >> n;for(int i = 0 ; i < n ; i ++){int x , y;cin >> x >> y;/* 核心 */ans = (ans + 1ll) * y % MOD * qsm(y - x, MOD - 2) % MOD;}cout << ans;return 0;
}