正题

题目链接:http://www.51nod.com/Contest/Problem.html#contestProblemId=305

题目大意

$n$个商铺，第$i$个商铺有pip_ipi​的概率营业，一个人从$1$走到$n$再走回来一直重复，如果走到没有人营业的商铺那么就结束。

求期望走多少个商铺后停下。

解题思路

我们可以先计算他走一个来回的期望停下位置$w$和不停下的概率$z$，那么我们就有式子
$$ans=w+z\ast ((2\ast n-2)+ans)$$
推导得
ans=w+z∗(2∗n−2)1−zans=frac{w+z*(2*n-2)}{1-z}ans=1−zw+z∗(2∗n−2)​

计算即可。

$code$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e6+10,XJQ=1e9+7;
ll n,p[N],a,b,c,w,z;
ll power(ll x,ll b)
{ll ans=1;while(b){if(b&1) ans=ans*x%XJQ;b>>=1;x=x*x%XJQ;}return ans;
}
int main()
{scanf("%lld%lld%lld%lld%lld",&n,&p[1],&a,&b,&c);for(ll i=2;i<=n;i++)p[i]=(p[i-1]*p[i-1]%XJQ*a%XJQ+p[i-1]*b%XJQ+c)%XJQ;z=1;for(ll i=1;i<=n;i++){(w+=z*p[i]%XJQ*(i-1)%XJQ)%=XJQ;z=z*(1-p[i]+XJQ)%XJQ; }for(ll i=n-1,k=n;i>1;i--,k++){(w+=z*p[i]%XJQ*k%XJQ)%=XJQ;z=z*(1-p[i]+XJQ)%XJQ; }printf("%lld",(w+z*(2*n-2)%XJQ)%XJQ*power((1-z+XJQ)%XJQ,XJQ-2)%XJQ);
}