题目大意
有一条很长很长的路（出题人的套路），你在(0)位置，你要去(h)位置。
路上有一些不同的位置上有敌人，你要和他战斗，你有(p)的概率赢。若你赢，则你可以走过去，否则你会死。还有很多个重生点。你每经过一个重生点有(p)的概率插旗。你死亡后你会在最后一个插旗的位置重生，然后该位置的旗子消失。如果没有旗子，则你在(0)位置重生。
求你走到目的地的期望路程。模({10}^9+7)
(nleq 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+pfrac1{E_{i+1}}}
]
[frac1{E_i}=frac1{E_{i+1}-pE_{i+1}+p}
]
[E_i=(1-p)E_{i+1}+p
]
然后把期望通过次数( imes)这段的长度加起来就好了。
时间复杂度：(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
",ans);
return 0;
}