[C++知识库] 【第十三届蓝桥杯C/C++研究生组】F-爬树的甲壳虫

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> 【第十三届蓝桥杯C/C++研究生组】F-爬树的甲壳虫 -> 正文阅读

[C++知识库]【第十三届蓝桥杯C/C++研究生组】F-爬树的甲壳虫

【第十三届蓝桥杯C/C++研究生组】 F-爬树的甲壳虫

- F 爬树的甲壳虫

F 爬树的甲壳虫

在这里插入图片描述

【样例1】
输入： 1 1 2
输出：2

【样例2】
输入： 3 1 2 3 5 7 11
输出：623902744

解题思路

先把他单独当作一个数学问题，求解时间的期望。（这里实名感谢俊鹏大佬的求解思路）
设从树的高度 $i$ 出发到树的顶端（高度 $n$ ）的时间期望为 $a_i$ ，则依题意可列出下面的递推关系：
$\left\{ \begin{aligned} a_n &= 0,\\ a_i &= (1-P_{i+1})a_{i+1} + P_{i+1}a_0 + 1, \quad i=0,1,...,n-1 \end{aligned} \right.$

简单解释一下第二个式子，即：要算 $a_i$ ，那么不妨先用一个单位的时间从位置 $i$ 爬到位置 $i + 1$ ，正好到达 $i + 1$ 时， $a_i$ 由如下两个情况转移而来，① 有 $P_{i+1}$ 的概率会滑落回位置 $0$ ，这样之后从位置 $0$ 开始到达树顶端的平均时间即 $a_0$ ；② 有 $1-P_{i+1})$ 的概率停留在位置 $i + 1$ ，此时状态变为了从位置 $i + 1$ 到树顶端的平均时间 $a_{i+1}$ 。两种情况的期望加权求和，并加上一个单位时间，即为 $a_i$ 。

我们的目标是求得 $a_0$ ，将以上递推关系的第二个式子变个形，递推下去并化简：
$\begin{aligned} & a_i = (1-P_{i+1})a_{i+1} + P_{i+1}a_0 + 1 \\ \Rightarrow & a_i-a_0=(1-P_{i+1})(a_{i+1}-a_0) + 1\\ \Rightarrow & a_{i+1}-a_0 =\frac{a_{i}-a_0}{1-P_{i+1}}-\frac{1}{1-P_{i+1}}\\ \Rightarrow & a_{i+1}-a_0 =\frac{a_{i-1}-a_0}{(1-P_{i+1})(1-P_{i})}-\frac{1}{1-P_{i+1}}-\frac{1}{(1-P_{i+1})(1-P_{i})}\\ \Rightarrow & ...\\ \Rightarrow & a_{i+1}-a_0 =0-\frac{1}{1-P_{i+1}}-\frac{1}{(1-P_{i+1})(1-P_{i})}-...-\frac{1}{\prod\limits_{j=1}^{i+1}(1-P_{j})}\\ \Rightarrow & a_{n}-a_0 =-a_0=-\frac{1}{1-P_{n}}-\frac{1}{(1-P_{n})(1-P_{n-1})}-...-\frac{1}{\prod\limits_{i=1}^{n}(1-P_{i})}\\ \Rightarrow & a_0=\frac{1}{1-P_{n}}+\frac{1}{(1-P_{n})(1-P_{n-1})}+...+\frac{1}{\prod\limits_{i=1}^{n}(1-P_{i})} \end{aligned}$

至此我们获得了问题所求期望的式子，这样问题就转化为了：给定 $a_0$ 的计算式， $P_i=x_i/y_i$ ，求 $a_0\bmod M$ ， $M$ 为所取的模，题目给定的 $M$ 为质数。

除法取余，需要用到除法逆元，假设要求 $\bmod M$ ， $M$ 为质数，且可以假定 $\gcd(b,M)=1$ 基本成立，则有费马小定理 $b^{M-1} \equiv 1 \bmod M$ ，稍微变下形（两端同乘以 $a / b$ ）可得： $\bmod M = a * b^{M-2} \bmod M$

其中， $?$ 为乘法运算符（不是卷积）。

下面，不妨先从和式的第 $1$ 项开始考虑，记为 $s_1$ ，即 $\begin{aligned}s_1\bmod M &=\frac{1}{1-P_{n}} \bmod M =\frac{1}{1-x_n/y_n} \bmod M\\&=\frac{y_n}{y_n-x_n}\bmod M\end{aligned}$

接着考虑 $s_2$ ，它可以由 $s_1$ 转移而来，即：

$\begin{aligned}s_2\bmod M&=\frac{s_1}{1-P_{n-1}} \bmod M =\frac{s_1}{1-x_{n-1}/y_{n-1}} \bmod M\\&=\frac{s_1*y_{n-1}}{y_{n-1}-x_{n-1}}\bmod M\end{aligned}$

依次类推，我们可以得到和式的递推关系式（同时用到除法逆元），如下：

$\begin{aligned}s_i\bmod M&=\frac{s_{i-1}*y_{n-i+1}}{y_{n-i+1}-x_{n-i+1}}\bmod M\\ &=s_{i-1}*y_{n-i+1}*(y_{n-i+1}-x_{n-i+1})^{M-2} \bmod M, \quad i=1,2,...,n\end{aligned}$

这样一来，我们的待求目标即 $a_0 \bmod M = \sum\limits_{i=1}^{n}(s_i \bmod M)$ 。

时间复杂度分析

对于和式的每一项 $s_i \bmod M$ ，其中的乘幂项可用快速幂算法在 $O(\log M)$ 的时间下算出，其余乘法在 $O (1)$ 下算出； $a_0$ 一共包含了 $n$ 项待求和的单元，故算法总体的时间复杂度为 $O (n l o g M)$ ，这样算法时间开销的数量级在 $10^6$ ，是可行的。

注：虽然这里单独将时间复杂度分析放在了思路后面，但实际上这是在设计算法思路前就应当考虑的，我们需要根据评测用例的规模来确定算法时间的上界。注意到，如果单独计算 $a_0$ 计算式的每一项，则计算除法的次数在 $O(n^2)$ 的量级，对于 $n=10^5$ ，这显然会超时，这样之后我们才会想到可以用上一个和式转移过来，减少重复计算。

C/C++算法实现

不多说了，直接上代码。

#include<bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int maxn = 1e5 + 5;
typedef long long LL;
int x[maxn], y[maxn];

// 快速幂 a^n % P 
LL fpow(LL a, int n, int P){
	LL res = 1;
	while (n){
		if(n&1)
			res = res * a % P;
		a = (a * a) % P;
		n >>= 1;
	}
	return res;
}

int main(){
	int n;
	scanf("%d", &n);
	for (int i=1; i<=n; ++i){	
		scanf("%d%d", &x[i], &y[i]);
	}
	// 计算s(i)和ans = a_0，pre = s(i-1)
	int ans = 0, pre = 1;
	for (int i=1; i<=n; ++i){
		pre = 1LL * pre * y[n-i+1] % MOD 
		* fpow(y[n-i+1]-x[n-i+1], MOD-2, MOD) % MOD;  // y >= x
		ans = (1LL * ans + pre) % MOD;
	}
	printf("%d\n", ans);
	return 0;
}