1. 2025: [蓝桥杯2022初赛] 爬树的甲壳虫

传送门：http://oj.ecustacm.cn/problem.php?id=2025

1.1. 题意

甲壳虫想要爬上高度为$n$的树，开始位于树根，高度为$0$，当它尝试从高度$i-1$爬到高度为$i$的位置时有$P_i$的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。

1.2. Tag

期望$DP$、逆元

1.3. 难度

☆☆☆☆

1.4. 思路

$dp[i-1]$表示从高度$i-1$出发到顶部花费的期望时间。根据题意可以得到如下的状态转移方程：

$dp[i-1]=P_i*dp[0]+(1-P_i)dp[i] + 1 \\ dp[n]=0$

利用递推式展开：

$dp[n]=0*dp[0]+0=a*dp[0]+b \\ dp[n-1]=P_n * dp[0] + (1-P_n)dp[n] + 1 \\ dp[n-2]=P_{n-1} * dp[0] + (1-P_{n-1})dp[n-1] + 1 \\ ... \\ dp[0]=P_1dp[0]+(1-P_1)dp[1]+1$

维护两个变量$a,b$，分别表示$dp[0]$的系数和常数，初始均为$0$。

将$dp[n]$代入$dp[n-1]$中，得到新的$a,b$：

$a=P_n+(1-P_n)*a \\ b=1+(1-P_n)*b$

最终可以得到：

$dp[0]=a*dp[0]+b$

遍历中全部使用模意义下的数字，求解$dp[0]$的时候相当于求解：

$(a-1)dp[0]+b\equiv0\% MOD$

利用扩展欧几里得求解$dp[0]$即可。

注意：存在更优的做法，递推过程更复杂，但是不需要最后的扩展欧几里得。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int MOD = 998244353;
ll x[maxn], y[maxn];
ll ksm(ll a, ll b, ll m){
    ll ans = 1;
    while(b)
    {
        if(b & 1)ans = ans * a % m;
        b >>= 1;
        a = a * a % m;
    }
    return ans;
}
ll inv(ll x){
    return ksm(x, MOD - 2, MOD);
}
ll extgcd(ll a, ll b, ll&x, ll&y){//ax+by = gcd(a, b)的解。返回值为gcd
    ll d = a;
    if(b)
    {
       d = extgcd(b, a % b, y, x);
       y -= (a / b) * x;
    }
    else x = 1, y = 0;
    return d;
}

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];
        ll g = __gcd(x[i], y[i]);
        x[i] = x[i] / g;
        y[i] = y[i] / g;
    }
    ll a = 0, b = 0;
    for(int i = n; i >= 1; i--)
    {
        ll p = x[i] * inv(y[i]) % MOD, p_1 = (y[i] - x[i]) * inv(y[i]) % MOD;
        a = (p + p_1 * a) % MOD;
        b = (1 + p_1 * b) % MOD;
    }
    ///cout<<x[1]<<" "<<y[1]<<" "<<inv(y[1])<<endl;
    ///dp[0] = a * dp[0] + b
    ///(a-1)dp[0]+k * MOD = MOD - b
    ///(a - 1)x + MOD * y = MOD - b
    ///cout<<a<<" "<<b<<endl;
    ll c = a - 1, d = MOD, x, y;
    ll g = extgcd(c, d, x, y);
    ///cout<<x<<" "<<y<<endl;
    ll x1 = x * (MOD - b) / g;
    ll y1 = y * (MOD - b) / g;
    cout<<(x1 % MOD + MOD ) % MOD<<endl;
    return 0;
}