xtq的棋盘-赛后题解

· · 题解

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(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)，得：

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

设F(i)=E(i)-E(i-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;
}