一开始是去想了对于相同的n,经过时间t-1的概率是否可以推出经过时间t的概率,尝试了很久都没推出来。
概率递推式的推导
假设当高度为k时,从树根爬到k所需要的期望时间是f(k)。
从f(k−1)出发,爬到高度为k有两种方式:
- 直接从k−1的位置多爬一格不掉下去;
- 从k−1个的位置多爬一个的时候先掉下去了,再从底部爬完k。(注意,并不一定是一次爬完,这中间也可能掉下去)
因此可以得出递推式:
f(k)=(f(k−1)+1)(1−pk)+(f(k−1)+1+f(k))pk,
其中,pk表示从k−1爬到k时会掉下去的概率。化简上式可以得到:
f(k)=f(k−1)+11−pk.
代入pk=xkyk,可得:
f(k)=yk(f(k−1)+1)yk−xk
所以可以用递推的方式求出答案。
初值
高度为0时需要的时间为0,即f(0)=0。
快速幂逆元
最后答案需要mod一个质数p=998244353。根据数论知识,除以一个数等于乘以它mod p意义下的逆元。又根据费马小定理,p为质数时,mod p意义下,inv(a)=ap−2 mod p,因此可以使用快速幂来辅助递推过程。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e5+5,p=998244353;
int n;
int f[N];
int a[N],b[N];
int qmi(int a,int k,int p){
int tmp=1;
while(k){
if(k&1)tmp=(ll)tmp*a%p;
k>>=1;
a=(ll)a*a%p;
}
return tmp;
}
int inv(int a){ return qmi(a,p-2,p);}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
f[0]=0;
for(int i=1;i<=n;i++){
f[i]=(1ll*f[i-1]+1)*b[i]%p*inv(b[i]-a[i])%p;
}
printf("%d\n",f[n]);
return 0;
}
这个递推式的推导很合理!比我的解释要好!
我有一个问题,我很疑惑为啥可以递推,因为你要从fk-1递推到fk,但是fk-1的值又和其他f1~n有关,因为可能从别的位置掉下去又爬上来,这样计算fk时可能要用到k之后的值,但是还没计算到啊,为啥
应该不用开数组吧,有点浪费空间了
如果写这样写是不是更美观fk−1+1
另外,f(k)的定义是不是有点问题
qaq可以细说吗
应该是:从树根开始,爬到高度k而不是顶端的时间期望值?
哦哦,是的,谢谢纠正
f(k)=(f(k−1)+1)(1−pk)+(f(k−1)+1+f(k))pk,请问这个式子的含义可以讲一下吗
f(k−1)+1这里为什么是+1
f(k−1)是爬到k-1不掉下去的期望时间,再往上爬一格时间+1
噢噢,不过确实不容易从题目中获取到这个点,👍