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

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

• • F 爬树的甲壳虫
  • • 解题思路
    • 时间复杂度分析
    • C/C++算法实现

F 爬树的甲壳虫

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

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

解题思路

先把他单独当作一个数学问题，求解时间的期望。（这里实名感谢俊鹏大佬的求解思路）
设从树的高度 i i i出发到树的顶端（高度 n n n）的时间期望为 a i a_i ai​，则依题意可列出下面的递推关系：
{ a n = 0 , a i = ( 1 − P i + 1 ) a i + 1 + P i + 1 a 0 + 1 , i = 0 , 1 , . . . , n − 1 \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. {an​ai​​=0,=(1−Pi+1​)ai+1​+Pi+1​a0​+1,i=0,1,...,n−1​

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

我们的目标是求得 a 0 a_0 a0​，将以上递推关系的第二个式子变个形，递推下去并化简：
a i = ( 1 − P i + 1 ) a i + 1 + P i + 1 a 0 + 1 ⇒ a i − a 0 = ( 1 − P i + 1 ) ( a i + 1 − a 0 ) + 1 ⇒ a i + 1 − a 0 = a i − a 0 1 − P i + 1 − 1 1 − P i + 1 ⇒ a i + 1 − a 0 = a i − 1 − a 0 ( 1 − P i + 1 ) ( 1 − P i ) − 1 1 − P i + 1 − 1 ( 1 − P i + 1 ) ( 1 − P i ) ⇒ . . . ⇒ a i + 1 − a 0 = 0 − 1 1 − P i + 1 − 1 ( 1 − P i + 1 ) ( 1 − P i ) − . . . − 1 ∏ j = 1 i + 1 ( 1 − P j ) ⇒ a n − a 0 = − a 0 = − 1 1 − P n − 1 ( 1 − P n ) ( 1 − P n − 1 ) − . . . − 1 ∏ i = 1 n ( 1 − P i ) ⇒ a 0 = 1 1 − P n + 1 ( 1 − P n ) ( 1 − P n − 1 ) + . . . + 1 ∏ i = 1 n ( 1 − P i ) \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} ⇒⇒⇒⇒⇒⇒⇒​ai​=(1−Pi+1​)ai+1​+Pi+1​a0​+1ai​−a0​=(1−Pi+1​)(ai+1​−a0​)+1ai+1​−a0​=1−Pi+1​ai​−a0​​−1−Pi+1​1​ai+1​−a0​=(1−Pi+1​)(1−Pi​)ai−1​−a0​​−1−Pi+1​1​−(1−Pi+1​)(1−Pi​)1​...ai+1​−a0​=0−1−Pi+1​1​−(1−Pi+1​)(1−Pi​)1​−...−j=1∏i+1​(1−Pj​)1​an​−a0​=−a0​=−1−Pn​1​−(1−Pn​)(1−Pn−1​)1​−...−i=1∏n​(1−Pi​)1​a0​=1−Pn​1​+(1−Pn​)(1−Pn−1​)1​+...+i=1∏n​(1−Pi​)1​​

至此我们获得了问题所求期望的式子，这样问题就转化为了：给定 a 0 a_0 a0​的计算式， P i = x i / y i P_i=x_i/y_i Pi​=xi​/yi​，求 a 0   m o d   M a_0\bmod M a0​modM， M M M为所取的模，题目给定的 M M M为质数。

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

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

下面，不妨先从和式的第 1 1 1项开始考虑，记为 s 1 s_1 s1​，即 s 1   m o d   M = 1 1 − P n   m o d   M = 1 1 − x n / y n   m o d   M = y n y n − x n   m o d   M \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} s1​modM​=1−Pn​1​modM=1−xn​/yn​1​modM=yn​−xn​yn​​modM​

接着考虑 s 2 s_2 s2​，它可以由 s 1 s_1 s1​转移而来，即：

s 2   m o d   M = s 1 1 − P n − 1   m o d   M = s 1 1 − x n − 1 / y n − 1   m o d   M = s 1 ∗ y n − 1 y n − 1 − x n − 1   m o d   M \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} s2​modM​=1−Pn−1​s1​​modM=1−xn−1​/yn−1​s1​​modM=yn−1​−xn−1​s1​∗yn−1​​modM​

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

s i   m o d   M = s i − 1 ∗ y n − i + 1 y n − i + 1 − x n − i + 1   m o d   M = s i − 1 ∗ y n − i + 1 ∗ ( y n − i + 1 − x n − i + 1 ) M − 2   m o d   M , i = 1 , 2 , . . . , n \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} si​modM​=yn−i+1​−xn−i+1​si−1​∗yn−i+1​​modM=si−1​∗yn−i+1​∗(yn−i+1​−xn−i+1​)M−2modM,i=1,2,...,n​

这样一来，我们的待求目标即 a 0   m o d   M = ∑ i = 1 n ( s i   m o d   M ) a_0 \bmod M = \sum\limits_{i=1}^{n}(s_i \bmod M) a0​modM=i=1∑n​(si​modM)。

时间复杂度分析

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

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

C/C++算法实现

不多说了，直接上代码。

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

哎，这么一看代码也不长，不过确实需要有足够的耐心去一步步分析。当时在求期望这一步就跪了，仍需努力！

注：目前能保证代码过样例，但不能保证算法是完全正确的（因为费马小定理要求模与除数互质，求解是建立在这条假设上的）。

以上分析若存有谬误，或者描述有不妥之处，恳请各位大佬们批评指正！