显然要用递推求解时间期望
设f[i]表示爬到第i层的时间期望,考虑用f[i-1]递推
直接爬上,$(1-P_i):f[i-1]+1$
摔下去,最终爬上,$P_i:f[i-1]+1+f[i]$
用期望公式得到:
$f[i]=(1-P_i)(f[i-1]+1)+P_i(f[i-1]+1+f[i])$
推出递推式:$f[i]=(1+f[i-1])/(1-P_i)$
剩下的问题就很好解决了,每次要对f[i]取模,而f[i]是个分数,用逆元的知识即可,$x/y(mod p)=xy^{-1}(mod p)$
而p是个质数,所以用费马小定理,$y^{-1}=y^{p-2}$
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N=100010;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
typedef long long LL;
typedef pair<int,int> PII;
int n,x,y;
LL f[N];
LL quick_pow(LL a,int k){
LL res=1;
while(k){
if(k&1) res=res*a%MOD;
a=a*a%MOD;
k>>=1;
}
return res;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x>>y;
LL a=y+(LL)y*f[i-1]%MOD;
LL b=y-x;
f[i]=a*quick_pow(b,MOD-2)%MOD;
}
cout<<f[n];
return 0;
}