[Kickstart Round B 2020 D. Wandering Robot] 数学题

1. 题目链接

Kickstart Round B 2020 D. Wandering Robot

2. 题目描述

3. 解题思路

枚举最开始接触被挖空四边形的上边界和左边界的前一步的概率。

然后当点 $(x,y)$ 不在四边形的下边界和右边界时，从点 $(1, 1)$ 到点 $(x, y)$ 的概率 $p_{x,y}$ 为

$$
\begin{align}
p_{x,y} &= \left(\frac{1}{2}\right)^{x+y-2}C_{x+y-2}^{x-1} \\
&= \frac{(x+y-2)!}{(x-1)!(y-1)!}\left(\frac{1}{2}\right)^{x+y-2}
\end{align}
$$

对于这种极大数乘以极小数的形式，可以通过先取对数函数，再通过指数函数还原，防止精度上溢和精度下溢。即

$$
\begin{align}
\log p_{x,y} &= \log[(x+y-2)!]-\log[(x-1)!]-\log[(y-1)!]-(x+y-2)\log2 \\
p_{x,y} &= \exp(\log p_{x,y})
\end{align}
$$

对于点$(x,y)$ 在四边形的下边界和右边界时，因为下边界上的点只能向右移动，右边届上的点只能向下移动，需要特殊处理一下，可以用递推求解。

复杂度 $\mathcal O(\min{W, H})$

4. 参考代码

#include 

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const long double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;

template<typename T>
void umax(T &a, const T b) { a = max(a, b); }

template<typename T>
void umin(T &a, const T b) { a = min(a, b); }

const int MAXN = 1e5 + 5;
int T, W, H, L, U, R, D;
long double las_w[MAXN], las_h[MAXN];
long double log_fac[MAXN];

long double calc_regular(int x, int y) {
    static long double const_log_2 = log((long double) 0.5);
    // C(x+y-2, x-1)*0.5^(x+y-2)
    if (x == 0 || y == 0) return 0;
    long double log_pred = log_fac[x + y - 2] - log_fac[x - 1] 
      - log_fac[y - 1] + (x + y - 2) * const_log_2;
    long double pred = exp(log_pred);
    return pred;
}

long double calc(int x, int y) {
    // check whether meets the borders
    if (x == 0 || y == 0) return 0;
    if (x == 1 && y == 1) return 1;
    if (x == W) return las_w[y];
    if (y == H) return las_h[x];
    return calc_regular(x, y);
}

int main() {
#ifdef __LOCAL_WONZY__
    freopen("input-4.txt", "r", stdin);
#endif
    log_fac[1] = 0;
    for (int i = 1; i < MAXN; ++i)
      log_fac[i] = log_fac[i - 1] + log((long double) i);
    cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        // W, H, L, U, R, D
        cin >> W >> H >> L >> U >> R >> D;
        if (W == 1) las_w[1] = 1;
        else las_w[1] = calc_regular(W - 1, 1) * 0.5;
        if (H == 1) las_h[1] = 1;
        else las_h[1] = calc_regular(1, H - 1) * 0.5;
        for (int i = 2; i < W; ++i) las_h[i] = las_h[i - 1] + calc_regular(i, H - 1) * 0.5;
        for (int j = 2; j < H; ++j) las_w[j] = las_w[j - 1] + calc_regular(W - 1, j) * 0.5;
        las_h[W] = las_w[H] = las_w[H - 1] + las_h[W - 1];
        long double ans = 0;
        // for (int j = U; j <= D; ++j) {
        // for (int j = 1; j <= H; ++j) {
        //     for (int i = 1; i <= W; ++i) {
        //         printf("%.5Lf ", calc(i, j));
        //     }
        //     printf("\n");
        // }
        for (int i = L; i <= R; ++i) {
            if (i == W) ans += calc(i, U - 1);
            else ans += calc(i, U - 1) * 0.5;
        }
        for (int j = U; j <= D; ++j) {
            if (j == H) ans += calc(L - 1, j);
            else ans += calc(L - 1, j) * 0.5;
        }
        ans = 1 - ans;
        printf("Case #%d: %.5Lf\n", cas, ans);
    }
    return 0;
}