思路
期望DP
状态表示:f[i]:从0到i的期望时间
状态计算:考虑从i - 1走到i,一次过的概率为(1 - pi),故期望次数为1 / (1 - pi),而每一次到i的耗时为f[i - 1] + 1,再将pi = y / x代入得f[i] = y * (f[i - 1] + 1) / (y - x)
初始化:f[0] = 0
快速幂求逆元
c++代码(O(nlogn))
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010,mod = 998244353;
int n;
LL f[N];
LL qmi(LL a,int k)
{
LL res = 1 % mod;
while(k)
{
if(k & 1) res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
f[0] = 0;
for(int i = 1;i <= n;i++)
{
LL x,y;
cin >> x >> y;
f[i] = y % mod * (f[i - 1] + 1) % mod * qmi(y - x,mod - 2) % mod;
}
cout << f[n] % mod << endl;
return 0;
}