13th蓝桥杯-爬树的甲壳虫

原题链接

题意

有一只甲壳虫想要爬上一颗高度为n的树，它一开始位于树根，高度为0

当它尝试从高度$i−1$爬到高度为$i$的位置时有$p_i$的概率会掉回树根，求它从树根爬到树顶时，经过的时间的期望值是多少。

思路

设$E[i]$为从点$i$到达点$n$的期望时间，则所求答案为$E[0]$

显然$E[n] = 0$

当$0\le i\le n - 1$时，$E[i] = p_i(E[0] + 1) + (1-p_i)(E[i + 1] + 1)......(1)$

注意，从$i$无论走到0还是走到$i + 1$，所花费的时间都是1

$E[n-1]$是$E[n]$和$E[0]$的函数，由于$E[n]$已知为0，所以$E[n-1]$是$E[0]$的一次函数

设$E[n-1] = A[n-1]E[0] + B[n-1]$

根据$(1)$式，$E[n-2],E[n-3],…E[0]$都是$E[0]$的一次函数

设$E[i] = A[i]E[0] + B[i]$

代入$(1)$式，记$1-p_i=q_i$，得$E[i] = p_iE[0] + q_i(A[i+1]E[0] + B[i + 1]) + 1 = (A[i+1]q_i + p_i)E[0] + B[i + 1]q_i+1$

所以$A[i] = A[i+1]q_i + p_i,\ B[i] = B[i + 1]q_i+1$

$i$从$n-1$循环到$0$，每次利用$A[i+1],B[i+1]$计算$A[i],B[i]$

最后的答案是$-B[0] / (A[0] - 1)$

题目中要求的分数取模，就是除法的时候使用乘法逆元

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, mod = 998244353;
int n, m;
LL x[N], y[N];

int qmi(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = (LL)res * a % mod;
        }
        a = (LL)a * a % mod;
        b >>= 1;
    }
    return res;
}

// E[i] = A[i]E[0] + B[i]
// E[n] = 0;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
        int d = __gcd(x[i], y[i]);
        x[i] /= d, y[i] /= d;
    }
    LL A = 0, B = 0; // 不必开数组A[],B[],只要开两个变量记录当前的A[i],B[i]即可
    for (int i = n - 1; i >= 0; i--)
    {
        LL p = x[i] * qmi(y[i], mod - 2) % mod, p1 = (LL)(y[i] - x[i]) * qmi(y[i], mod - 2) % mod;
        A = (A * p1 % mod + p) % mod, B = (B * p1 % mod + 1) % mod;
    }
    LL ans = ((LL)-B * qmi(A - 1, mod - 2) % mod + mod) % mod;
    // LL ans = (B * qmi(1 - A, mod - 2) % mod + mod) % mod; // 这样求也可以
    cout << ans << '\n';
    return 0;
}