自动搬运

查看原文

来自洛谷，原作者为

	Caro23333 Dream Theater 脑残粉

搬运于2025-08-24 22:07:50，当前版本为作者最后更新于2018-12-20 20:35:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

20pts:

感性理解数学期望的定义，我们可以采用多次模拟随机过程的的暴力方法来算出数据很小时的期望值。

事实上，对于题目中给出的数据范围只需要模拟10000次随机过程并且计算平均的时间再四舍五入即可准确得到答案而不超出时限。

40pts:

接下来我们设向左走的概率为$p$。

考虑一个期望的线性方程组。

设$E(x)$为从$x$开始到达$0$所需要的期望时间，有：

$E(0)=0$

$E(1)=pE(0)+(1-p)E(2)+1$

$E(2)=pE(1)+(1-p)E(3)+1$

$\dots \dots$

$E(n-1)=pE(n-2)+(1-p)E(n)+1$

$E(n)=E(n-1)+1$

使用高斯消元在模意义下解这个方程组，答案为$E(m)$。

70pts:

发现$E(i)$只和$E(i-1)$与$E(i+1)$相关，而$E(0)=0$，所以有：

$E(1)=(1-p)E(2)+1$。 代入第三个方程，得到：

$E(2)=p((1-p)E(2)+1)+(1-p)E(3)+1$， 就可以推出$E(2)$和$E(3)$的关系，然后再代入下一个方程，依此类推，可以在$O(n)$时间内从上到下进行消元，解出$E(n)$。

然后可以再用$O(n)$时间从下到上推回来，就可以推出$E(m)$。

100pts:

考虑第$i+1$个方程$E(i)=pE(i-1)+(1-p)E(i+1)+1$，变形可得： $(1-p)E(i+1)-E(i)=-pE(i-1)+1$

两侧同时加上$pE(i)$，得： $(1-p)[E(i+1)-E(i)]=p[E(i)-E(i-1)]+1$，即：

$E(i)-E(i-1)=\frac{1-p}{p}[E(i+1)-E(i)]+\frac{1}{p}$

设$F(i)=E(i)-E(i-1)$， 则有： $F(i)=\frac{1-p}{p}F(i+1)+\frac{1}{p}$，并且$F(n)=1$。

有一定技巧性的一步：将式子的两侧同时加上$\frac{1}{1-2p}$（此时要求$p$不等于$\frac{1}{2}$），得到： $F(i)+\frac{1}{1-2p}=\frac{1-p}{p}[F(i+1)+\frac{1}{1-2p}]$（此步来源可上网搜索"特征根法"）

那么显然有：$F(i)=(\frac{1-p}{p})^{n-i}[F(n)+\frac{1}{1-2p}]-\frac{1}{1-2p}$

我们发现$E(m)=\sum_{i=1}^{m}F(i)$，实际上核心就是一个等比数列求和。

对于一个首项为$a$，公比为$q$，项数为$n$的等比数列，它的各项和$S=\frac{a(1-q^n)}{1-q}$，利用这个公式对$F(i)$进行求和即可得到$E(m)$，限于篇幅就不详述了。

之前暂时没有考虑$p=\frac{1}{2}$的情况，但我们发现这种情况下$\frac{1-p}{p}=1$，也就是说$F(i)=F(i+1)+2$。

那么，$\sum_{i=1}^{m}F(i)$就变成了一个非常naive的等差数列求和了。

此题完结。

代码：

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define mod 1000000007

using namespace std;
typedef long long ll;
inline ll qpow(ll a, ll b)
{
    ll res = 1;
    while(b)
    {
        if(b&1) res = res*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return res;
}
inline ll inv(ll x)
{
    return qpow(x,mod-2);
}
ll prb,qrb,rrb;
inline ll calc(ll x)
{
    return ((1-qpow(qrb,x))%mod+mod)%mod*inv(((1-qrb)%mod+mod)%mod)%mod;
}

int main()
{
    ll n,m,p,q;
    cin >> n >> m >> p >> q;
    prb = p*inv(q)%mod;
    qrb = ((1-prb)%mod+mod)%mod*inv(prb)%mod;
    rrb = (mod-1)*inv(((1-2*prb%mod)%mod+mod)%mod)%mod;
    if(q==2&&p==1)
        cout << ((2*n%mod-m)%mod+mod)%mod*m%mod << endl;
    else
    {
        ll ans = ((1-rrb)%mod+mod)%mod;
        ans = ans*(((calc(n)-calc(n-m))%mod+mod)%mod)%mod;
        ans = (ans+(m*rrb)%mod)%mod; 
        cout << ans << endl;
    }
    return 0;
}