有一只甲壳虫想要爬上一颗高度为?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 2
2
3
1 2
3 5
7 11
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
#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;
}