题目如下：

在这里插入图片描述

思路 or 题解：

概率DP

状态定义：

dp[i]dp[i]dp[i] 表示从树根到第 iii 层的期望

状态转移：

dp[i]=(dp[i−1]+1)∗11−pdp[i] = (dp[i - 1] + 1) * \frac{1}{1-p}dp[i]=(dp[i−1]+1)∗1−p1
这个式子的意思是：从第 000 层出发，到第 iii 层的期望时间 E(i)E(i)E(i) 可以通过从第 000 层到第 i−1i-1i−1 层的期望时间 E(i−1)E(i-1)E(i−1) 加上一次上升所需要的期望时间（即 111）再乘以 11−p\frac{1}{1-p}1−p1。

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

简单解释一下这个 11−p\frac{1}{1-p}1−p1
以第一个样例为例子：
期望 = 1∗12+2∗14+3∗18....1 * \frac{1}{2} + 2 * \frac{1}{4} + 3 * \frac{1}{8} ....1∗21+2∗41+3∗81....
收敛与 11−p\frac{1}{1-p}1−p1

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

答案计算

DP递推

AC 代码如下：

/*
Make it simple and keep self stupid
author：Joanh_Lan
*/
#pragma GCC optimize(3)
#pragma GCC optimize("inline") // 如果比赛允许开编译器优化的话，可以默写这两段
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define buff                     \ios::sync_with_stdio(false); \cin.tie(0);
#define int long long
#define ll long long
#define PII pair
#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();
}

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：Hive---拉链表

下一篇：LogCompilation后JIT输出文件格式解析

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

题目如下：

思路 or 题解：

状态定义：

状态转移：

答案计算

AC 代码如下：

相关内容

热门资讯

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

题目如下：

思路 or 题解：

状态定义：

状态转移：

答案计算

AC 代码如下：

相关内容

热门资讯

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