题目大意
有一条很长很长的路（出题人的套路），你在\(0\)位置，你要去\(h\)位置。
路上有一些不同的位置上有敌人，你要和他战斗，你有\(p\)的概率赢。若你赢，则你可以走过去，否则你会死。还有很多个重生点。你每经过一个重生点有\(p\)的概率插旗。你死亡后你会在最后一个插旗的位置重生，然后该位置的旗子消失。如果没有旗子，则你在\(0\)位置重生。
求你走到目的地的期望路程。模\({10}^9+7\)
\(n\leq 100000\)
题解
这道题我用的式子和题解的不一样，最后推出来同一个式子。
设\(E_i=\)第\(i\)段的期望通过次数，\(f_i=\)结算完第\(i\)个事件后不回到第\(i\)个点直接到达终点的概率。
根据期望与概率的关系，有：\(E_i=\frac1{f_i}\)
设\(p=\frac{a_{i+1}}{b_{i+1}}\)（即下一个事件发生的概率）
若下一个事件是'\(X\)'（敌人）：
\[f_i=pf_{i+1}
\]
\]
\[\frac1{E_i}=\frac1{pE_{i+1}}
\]
\]
\[E_i=\frac{E_{i+1}}p
\]
\]
若下一个事件是'\(F\)'（重生点）：
\[f_i=f_{i+1}(1+p(1-f_{i+1})+p^2{(1-f_{i+1})}^2+\cdots)=f_{i+1}\frac1{1-p(1-f_{i+1})}=f_{i+1}\frac1{1-p+pf_{i+1}}
\]
\]
（第一次成功+第一次插旗&失败&第二次成功+前两次插旗&失败&第三次成功...）
\[\frac1{E_i}=\frac1{E_{i+1}}\frac1{1-p+p\frac1{E_{i+1}}}
\]
\]
\[\frac1{E_i}=\frac1{E_{i+1}-pE_{i+1}+p}
\]
\]
\[E_i=(1-p)E_{i+1}+p
\]
\]
然后把期望通过次数\(\times\)这段的长度加起来就好了。
时间复杂度：\(O(n)\)
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll p=1000000007;
ll fp(ll a,ll b)
{
ll s=1;
while(b)
{
if(b&1)
s=s*a%p;
a=a*a%p;
b>>=1;
}
return s;
}
ll c[100010],a[100010],b[100010],d[100010];
ll f[100010];
int main()
{
ll h,n;
scanf("%lld%lld",&h,&n);
int i;
char s[10];
for(i=1;i<=n;i++)
{
scanf("%s",s);
if(s[0]=='X')
c[i]=1;
else
c[i]=2;
scanf("%lld%lld%lld",&d[i],&a[i],&b[i]);
a[i]=a[i]*fp(b[i],p-2)%p;
}
f[n]=1;
for(i=n;i>=1;i--)
if(c[i]==1)
f[i-1]=f[i]*fp(a[i],p-2)%p;
else
f[i-1]=((1-a[i]+p)%p*f[i]%p+a[i])%p;
d[0]=0;
d[n+1]=h;
ll ans=0;
for(i=0;i<=n;i++)
ans=(ans+(d[i+1]-d[i])%p*f[i]%p+p)%p;
printf("%lld\n",ans);
return 0;
}