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