「GYM102059C」Dstorv

发表于 | 更新于 | 分类于 | 阅读次数：

题意简述

GYM 102059C

数轴上有 $n$ 个人，每人以相同速度向左或右移动。两人相遇则会有一人消失。向左的人消失概率为 $h$，向右的人消失概率为 $r = 1 - h$。
给定每个人的移动方向，求最终恰好剩下 $A$ 个向左的人和 $B$ 个向右的人的概率。（$n\le 5000$。）

主要思路

注意到每种最终的状态都有唯一的分界点，其左边全都是向左的人，右边全都是向右的人。

不妨考虑 dp 出每个前缀剩下 $A$ 个向左的人的概率，每个后缀剩下 $B$ 个向右的人的概率，然后枚举分界点求出答案。

这里以前缀为例，设 $f(i, j)$ 表示前 $i$ 个人右边加上 $j$ 个向左的人后，剩余 $A$ 个向左的人的概率。

考虑第 $i$ 个人的方向：

  • 向左，则 $f(i, j) = f(i - 1, j + 1)$。
  • 向右，则 $f(i, j) = [j > 0]\cdot(h\cdot f(i, j - 1) + r\cdot f(i - 1, j))$。

显然有初始 $f(0, A) = 1$。于是轻松愉快地获得了 $O(n^2)$ 复杂度。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
typedef long long i64;
#define Templ(T) template <typename T>
inline int read() {
    Rint ans = 0;
    reg char c = getchar();
    while (!isdigit(c)) c = getchar();
    for (; isdigit(c); c = getchar())
        ans = ans * 10 + c - '0';
    return ans;
}
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
#define mod 1000000007
inline int ksm(int x, int y) {
    int res = 1;
    for (; y; y >>= 1, x = 1ll * x * x % mod)
        if (y & 1) res = 1ll * res * x % mod;
    return res;
}
inline void qmo(int &x){ x += x >> 31 & mod; }
} // namespace my_std
using namespace my_std;

#define N 5010
inline int init_n(){
    return read();
}
inline int init_R(){
    int a(read()), b(read());
    return (i64)a * ksm(a + b, mod - 2) % mod;
}
inline int init_H(const int &r){
    int a = 1 - r;
    qmo(a);
    return a;
}
const int n(init_n());
const i64 R(init_R()), H(init_H(R));
//R: right, H: left
int rf[N][N], hf[N][N];
int Rl, Hl;
char s[N];

int main() {
    scanf("%s", s + 1);
    Rl = read(), Hl = read();

    hf[0][Hl] = 1;
    FOR(i, 1, n){
        if(s[i] == 'H'){
            // FOR(j, 0, n) hf[i][j] = hf[i - 1][j + 1];
            memcpy(hf[i], hf[i - 1] + 1, sizeof(int) * (n + 1));
        }else{
            FOR(j, 1, n){
                hf[i][j] = (R * hf[i - 1][j] + H * hf[i][j - 1]) % mod;
            }
        }
    }

    rf[n + 1][Rl] = 1;
    ROF(i, n, 1){
        if(s[i] == 'R'){
            // FOR(j, 0, n) rf[i][j] = rf[i + 1][j + 1];
            memcpy(rf[i], rf[i + 1] + 1, sizeof(int) * (n + 1));
        }else{
            FOR(j, 1, n){
                rf[i][j] = (H * rf[i + 1][j] + R * rf[i][j - 1]) % mod;
            }
        }
    }

    Rint res(0);
    FOR(i, 0, n) qmo(res += (i64)hf[i][0] * rf[i + 1][0] % mod - mod);
    printf("%d\n", res);
    return 0;
}