题目链接：https://www.luogu.com.cn/problem/P8774
思路：
设 \(f_i\) 为甲壳虫从高度 \(i\) 到达高度 \(n\)
因为从高度 \(i\) 走 \(1\) 步有 \(1-P_{i+1}\) 的概率到达高度 \(i+1\)，有 \(P_{i+1}\) 的概率到达高度 \(0\)，所以：
\(f_i = 1 + (1 - P_{i+1}) \times f_{i+1} + P_{i+1} \times f_0\)
可以高斯消元，但是高斯消元没咋写过啊
\(f_0 = (1-P_1) f_1 + P_1 f_0 + 1\)
\(f_1 = (1-P_2) f_2 + P_2 f_0 + 1\)
\(f_2 = (1-P_3) f_3 + P_3 f_0 + 1\)
\(\ldots\)
\(f_{n-1} = (1-P_n) f_n + P_n f_n + 1\)
\(f_n = 0\)
考虑 \(f_0\)
令 \(X = P_1 + (1-P_1) P_2 + (1-P_1)(1-P_2) P_3 + \ldots (1-P_1)(1-P_2) \cdots (1-P_{n-1}) P_n\)
考虑常数项：
令 \(Y = 1 + (1-P1) + (1-P_1)(1-P2) + \ldots + (1-P_1)(1-P_2) \cdots (1-P_{n-1})\)
所以
\(f_0 = X f_0 + Y\)
\(f_0 = \dfrac{Y}{1 - X}\)
示例程序：
#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
typedef long long ll;
void gcd(ll a , ll b , ll &d , ll &x , ll &y) {
if(!b) {d = a; x = 1; y = 0;}
else { gcd(b , a%b,d,y , x); y -= x * (a/b); }
}
ll inv(ll a , ll n = mod) {
ll d , x , y;
gcd(a , n , d, x , y);
return d == 1 ? (x+n)%n : -1;
}
const int maxn = 1e5 + 5;
int n;
long long x[maxn], y[maxn], p[maxn];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", x+i, y+i);
p[i] = x[i] * inv(y[i]) % mod;
}
ll X = p[1], Y = 1, tmp = 1;
for (int i = 2; i <= n; i++) {
// tmp = tmp * (1 - p[i-1] + mod) % mod;
tmp = tmp * (y[i-1] - x[i-1]) % mod * inv(y[i-1]) % mod;
X = (X + tmp * p[i] % mod) % mod;
Y = (Y + tmp) % mod;
}
ll ans = Y * inv((1 - X + mod) % mod) % mod;
printf("%lld\n", ans);
return 0;
}