第十三届蓝桥杯省赛C++ A组爬树的甲壳虫(简单概率DP)

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

题目如下

在这里插入图片描述

思路 or 题解

概率DP

状态定义

$d p [i]$ 表示从树根到第 $i$ 层的期望

状态转移

$\frac{1}{1-p}$
这个式子的意思是从第 $0$ 层出发到第 $i$ 层的期望时间 $E (i)$ 可以通过从第 $0$ 层到第 $i - 1$ 层的期望时间 $E (i - 1)$ 加上一次上升所需要的期望时间即 $1$ 再乘以 $\frac{1}{1-p}$ 。

在期望中 $1/ (1 - p)$ 表示一个事件在不停地进行下去直到该事件发生为止所需的期望次数。

简单解释一下这个 $\frac{1}{1-p}$
以第一个样例为例子
期望 = $\frac{1}{2} + 2 * \frac{1}{4} + 3 * \frac{1}{8} ....$
收敛与 $\frac{1}{1-p}$

这个式子是 等差 $\times$ 等比
具体如何得到再此不再多赘述。

答案计算

DP递推

AC 代码如下

/*
Make it simple and keep self stupid
authorJoanh_Lan
*/
#pragma GCC optimize(3)
#pragma GCC optimize("inline") // 如果比赛允许开编译器优化的话可以默写这两段
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <bitset>
#include <set>
#include <random>
#include <ctime>
#include <queue>
#include <stack>
#include <climits>
#define buff                     \
    ios::sync_with_stdio(false); \
    cin.tie(0);
#define int long long
#define ll long long
#define PII pair<int, int>
#define px first
#define py second
typedef std::mt19937 Random_mt19937;
Random_mt19937 rnd(time(0));
using namespace std;
const int mod = 998244353;
const int inf = 2147483647;
const int N = 100009;
int Mod(int a,int mod){return (a%mod+mod)%mod;}
//int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
//int lcm(int a,int b){return a*b/__gcd(a,b);}
int n;
void solve()
{
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int a, b;	cin >> a >> b;
		ans = ((ans + 1) * b) % mod * inv(b - a, mod) % mod;
	}
	cout << ans << '\n';
}
signed main()
{
	buff;
	int _ = 1;
	// cin >> _;
	while (_--)
		solve();
}