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

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

1.1. 题意

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

1.2. Tag

期望、逆元

1.3. 难度

☆☆☆☆

1.4. 思路

表示从高度出发到顶部花费的期望时间。根据题意可以得到如下的状态转移方程:

利用递推式展开:

维护两个变量,分别表示的系数和常数,初始均为

代入中,得到新的

最终可以得到:

遍历中全部使用模意义下的数字,求解的时候相当于求解:

利用扩展欧几里得求解即可。

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

#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;
}

results matching ""

    No results matching ""