2022第13届蓝桥杯cc++A组E题爬树的甲壳虫【概率期望+乘法逆元】_C

2022第13届蓝桥杯c/c++A组E题爬树的甲壳虫【概率期望+乘法逆元】

分析

先考虑求从0到1的期望。

有 p p p₁的概率掉落， 1 − p 1 1-p_1 1−p1的概率向上移动一次
只走一次上去的期望时间是 1 ∗ ( 1 − p 1 ) 1*(1-p_1) 1∗(1−p1)
只走两次上去的期望时间是 2 ∗ ( 1 − p 1 ) ∗ p 1 2*(1-p_1)*p_1 2∗(1−p1)∗p1
只走三次上去的期望时间是 3 ∗ ( 1 − p 1 ) ∗ p 1 2 3*(1-p_1)*p_1^2 3∗(1−p1)∗p12
…
所以期望时间是 E x ( 1 ) = ∑ i = 1 i ∗ ( 1 − p 1 ) ∗ p 1 i − 1 = ( 1 − p 1 ) ∗ ∑ i = 1 i ∗ p 1 i − 1 E_x(1)=\sum_{i=1}i*(1-p_1)*p_1^{i-1}=(1-p_1)*\sum_{i=1}i*p_1^{i-1} Ex(1)=∑i=1i∗(1−p1)∗p1i−1=(1−p1)∗∑i=1i∗p1i−1
令 F ( x ) = ∑ x = 1 x ∗ p 1 x − 1 F(x)=\sum_{x=1}x*p_1^{x-1} F(x)=∑x=1x∗p1x−1则 F ( x ) = ∑ x = 1 ( p 1 x ) ′ = （ ∑ x = 1 p 1 x ) ′ F(x)=\sum_{x=1}(p_1^{x})^{'}=（\sum_{x=1}p_1^{x})^{'} F(x)=∑x=1(p1x)′=（∑x=1p1x)′
显然, F ( x ) F(x) F(x)是首项为 p 1 p_1 p1的等比数列求和，运用等比数列求和公式可得 F ( x ) = ( 1 − p 1 ∞ 1 − p 1 ) ′ F(x)=(\frac{1-p_1^\infty}{1-p_1})^{'} F(x)=(1−p11−p1∞)′因为 p 1 < 1 p_1<1 p1<1所以 F ( x ) = ( 1 1 − p 1 ) ′ = 1 ( 1 − p 1 ) 2 F(x)=(\frac{1}{1-p_1})^{'}=\frac{1}{(1-p_1)^2} F(x)=(1−p11)′=(1−p1)21
所以， E x ( 1 ) = ( 1 − p 1 ) ∗ 1 ( 1 − p 1 ) 2 = 1 1 − p 1 E_x(1)=(1-p_1)*\frac{1}{(1-p_1)^2}=\frac{1}{1-p_1} Ex(1)=(1−p1)∗(1−p1)21=1−p11
那么从n-1到n的期望时间分析如下：
一次上去的期望时间是( E x ( n − 1 ) + 1 ) ∗ ( 1 − p n ) E_x(n-1)+1)*(1-p_n) Ex(n−1)+1)∗(1−pn)
两次上去的期望时间是( 2 ∗ （ E x ( n − 1 ) + 1 ) ) ∗ ( 1 − p n ) ∗ p n 2*（E_x(n-1)+1))*(1-p_n)*p_n 2∗（Ex(n−1)+1))∗(1−pn)∗pn(理解为第一次掉下去，第二次上去)
三次上去的期望时间是( 3 ∗ （ E x ( n − 1 ) + 1 ) ) ∗ ( 1 − p n ) ∗ p n 2 3*（E_x(n-1)+1))*(1-p_n)*p_n^2 3∗（Ex(n−1)+1))∗(1−pn)∗pn2(理解为前两次掉下去，第三次上去)
…
那么，同理可得 E x ( n ) = ( E x ( n − 1 ) + 1 ) ∗ ∑ i = 1 i ∗ p n i − 1 = ( E x ( n − 1 ) + 1 ) ∗ 1 1 − p n E_x(n)=(E_x(n-1)+1)*\sum_{i=1}i*p_n^{i-1}=(E_x(n-1)+1)*\frac{1}{1-p_n} Ex(n)=(Ex(n−1)+1)∗∑i=1i∗pni−1=(Ex(n−1)+1)∗1−pn1

即得到递推式 E x ( n ) = ( E x ( n − 1 ) + 1 ) ∗ 1 1 − p n E_x(n)=(E_x(n-1)+1)*\frac{1}{1-p_n} Ex(n)=(Ex(n−1)+1)∗1−pn1 即 E x ( n ) = ( E x ( n − 1 ) + 1 ) ∗ y i y i − x i E_x(n)=(E_x(n-1)+1)*\frac{y_i}{y_i-x_i} Ex(n)=(Ex(n−1)+1)∗yi−xiyi

对于除以 ( y i − x i ) (y_i-x_i) (yi−xi)在 m o d P mod\space P mod P的意义下等价于乘以 ( y i − x i ) − 1 (y_i-x_i)^{-1} (yi−xi)−1，由于 P P P为质数，根据费马小定理，运用快速幂求逆元。

整体代码如下

#include
using namespace std;
const int MAXN=100010;
const long long Mod =998244353ll;
int n;
long long ans=0;
long long quickpow(long long x, long long y)
{
	long long re=1ll;
	while(y)
	{
		if(y&1ll) re=re*x%Mod;
		x=x*x% Mod;
		y>>=1;
	}
	return re;
}

int main()
{
	long long x, y;
	scanf("%d",&n);
	for(long long i=1ll;i<=n;i++)
	{
		scanf("%lld%lld",&x,&y);
		ans=(ans+1ll)*y%Mod*quickpow(y-x,Mod-2ll)%Mod;
		ans=(ans+Mod)%Mod;
	}
	printf("%lld",ans);
	return 0;
}