Brief description:

。。一维随机游动系列问题，向右的概率为 r，向左的概率为 l，静止的概率为 s。
询问 n 步后 rightmost (历史上的最右位置) 的期望。

Analysis:

… 接上文。。）
我看到提交记录里有个 93ms 的程序。。。可见低于 O(n3) 的做法是存在的。。。

首先要用到广义 Catalan 数。。
。Catalan(n, m, k): 宽 n、 长 m 不越过对角线的方案数。。对角线向上平移 k 格。。。。。。结果是

$$!\binom{n+m}{n} – \binom{n+m}{n+k+1}$$。

证明参考镜像法。。。
。。(另对 k = 0 的情况…参见。。RQ 293. 网格

下面考虑优化 O(n3) 的复杂度。。方法是枚举 rightmost。
。。然后我们设法计算出对应的概率。。
由于随机移动过程对应过去的时候。。并不保证一定停留在某个 (n, m) 。。所以我们还有再枚举求和一次。。。
。。。。这样解决了 l = r = 0.5 的情况。。

。。在考虑时滞之后我的结果就不对了。。但是也可能是之前就错了。。(而且目前是枚举时滞。。总计复杂度已经是 O(n3) 了。。。。
。。下面的代码有 bug。。。

//}/* .................................................................................................................................. */

const int N = 1009;
DB C[N][N], l, r, s;
int n;

DB Catalan(int n, int m, int k){ // 广义卡塔兰序列
    assert(m-n<=k);
    return C[n+m][n] - (n+k+1 <= n+m ? C[n+m][n+k+1] : 0);
}

DB Probfact(int a, int b){
    return pow(l, a) * pow(r, b);
}

DB g(int k){ // rightmost <= k 的概率
    DB res = 0;

    REP(i, n+1){
        if (2*i-n>k) break;
        res += Catalan(n-i, i, k) * Probfact(n-i, i);
    }

    return res;
}

DB p(int k){ // rightmost 为 k 的概率
    return g(k) - g(k-1);
}

DB f(int n){
    DB res = 0; REP_1(i, n){
        //cout << i << ":" << p(i) << endl;
        res += i * p(i);
    }
    return res;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    REP(i, N){C[i][0] = 1; REP_1(j, i) C[i][j] = C[i-1][j-1] + C[i-1][j];}

    Rush{
        scanf("%*d%d", &n);
        RF(l, r); s = 1 - l - r; l /= 1-s, r /= 1-s;
        DB res = 0; REP(i, n+1) res += f(n-i) * C[n][i] * pow(s, i) * pow(1-s, n-i); // 枚举时滞。
        OT(res);
    }
}

完整 bug 代码。。

External link:

.. .

Posted by xiaodao
Category: UVa