题目描述
有一只甲壳虫想要爬上一颗高度为 $n$的树,它一开始位于树根,高度为 $0$
,当它尝试从高度 $i−1$爬到高度为$i$的位置时有$pi$的概率会掉回树根,求它从树根爬到树顶时,经过的时间的期望值是多少。
样例
3
1 2
3 5
7 11
623902744
不会打公式,全部写纸上了,感觉很容易懂
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define endl "\n"
void solve()
{
int n;
cin >> n;
vector<int> dp(n + 5), x(n + 5), y(n + 5);
for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
const int mod = 998244353;
auto qmod = [&](int a, int b)
{
int res = 1;
while (b)
{
if (b % 2) res *= a, res %= mod;
b /= 2;
a *= a, a %= mod;
}
return res;
};
auto inv = [&](int x)
{
return qmod((x % mod + mod) % mod, mod - 2);
};
auto p = [&](int i)
{
return x[i] * inv(y[i]) % mod;
};
vector<int> r(n + 5), s(n + 5);
r[0] = 1;
for (int i = 1; i <= n; i++)
{
//dp[i]=(dp[i-1]-((1+p[i]*dp[0]))/(1-p[i])
//对于r:r[i]=(r[i-1]-p[i])/(1-p[i])
//对于s:s[i]=(s[i-1]-1)/(1-p[i])
r[i] = r[i - 1] - p(i);
s[i] = s[i - 1] - 1;
r[i] *= inv(1 - p(i));
s[i] *= inv((1 - p(i)));
r[i] = (r[i] % mod + mod) % mod;
s[i] = (s[i] % mod + mod) % mod;
}
int aa = (-s[n] * inv(r[n]));
//dp[n]=r[n]*dp[0]+s[n]=0,dp[0]=s[n]/(-r[n])
aa = (aa % mod + mod) % mod;
cout << aa << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while (t--)
solve();
}
写的真棒,博主太厉害了
什么自买自夸