F题详细题解+拓展题单

在数组上移动，要从1走到n
在第i个下标，有p1[i]的概率走到i+1，有p2[i]的概率走到i，有p3[i]的概率走到i-1
下标1另外算，p的概率走到2，则1走到2的期望步数是1/p
求从1走到n的期望步数
令e(u,u+1)表示从u走到u+1的期望步数
根据题目，有递推式
e(u,u+1)=p1[u]*(e(u+1,u+1)+1) + p2[u]*(e(u,u+1)+1) + p3[u]*(e(u-1,u+1)+1)
根据期望的线性性质e(u-1,u+1)=e(u-1,u)+e(u,u+1)
则原式子等于
e(u,u+1)=p1[u]*(e(u+1,u+1)+1) + p2[u]*(e(u,u+1)+1) + p3[u]*(e(u-1,u)+e(u,u+1)+1)
移项整理得到
e(u,u+1)= (p1[u]+p2[u]+p3[u]+p3[u]*e(u-1,u))/(1-p2[u]-p3[u])
最后要求的实际上是 e(1,n)，也就是我们求出的e数组之和
另外再加个1就可以了 


n=ii()
a=li()
b=li()
p1=[0]*n
p2=[0]*n
p3=[0]*n
for i in range(1,n-1):
    inv=pow((a[i]+b[i])**2,mod-2,mod)
    p1[i]=a[i]*a[i]*inv%mod
    p2[i]=2*a[i]*b[i]*inv%mod
    p3[i]=b[i]*b[i]*inv%mod
e=[0]*n
p=a[0]*pow(a[0]+b[0],mod-2,mod)%mod
e[0]=pow(p,mod-2,mod)
for i in range(1,n-1):
    e[i]=(p1[i]+p2[i]+p3[i]+p3[i]*e[i-1])*(1-p2[i]-p3[i],mod-2,mod)%mod
print(sum(e)%mod)

类似的推柿子题目