CodeForces 708E Student's Camp

有一个 $(n + 2) \times m$ 的长方形，除了第一行和最后一行，其他每一行每一天最左边和最右边的格子都有 $p$ 的概率被摧毁，每行之间独立且左边和右边独立，求 $k$ 天之后最上面一行与最下面一行四联通的概率。

其中 $1 \leq n, m \leq 1500, 0 \leq k \leq 10^{5}$ ，答案对 $10^{9} + 7$ 取模。

一个简单的想法就是我们令 $h_{i, l, r}$ 表示 $k$ 天后第 $i$ 行还剩下 $[l, r]$ ，前 $i$ 行联通的概率。 $P_{l, r}$ 表示单独一行只剩 $[l, r]$ 的概率。

首先我们有：

h_{i, l, r} = P_{l, r} \sum_{[l, r] \cap [l^{'}, r^{'}] \neq \emptyset} h_{i - 1, l^{'}, r^{'}}

接下来我们考虑 $P_{l, r}$ ，我们令 $q_{i} = (\binom{k}{i}) p^{i} (1 - p)^{k - i}$ ，不难发现：

P_{l, r} = q_{l - 1} q_{m - r}

然后我们令 $f_{i, r}$ 表示右端点为 $r$ 的所有 $h$ 之和，同理 $g_{i, l}$ 表示以左端点为 $l$ 的所有 $h$ 之和，再令 $F_{i, r}$ 表示右端点小于等于 $r$ 的所有 $h$ 之和，同理 $G_{i, l}$ 表示以左端点大于等于 $l$ 的所有 $h$ 之和。

具体地：

\begin{aligned} f_{i, r} & = \sum_{l = 1}^{r} h_{i, l, r} \\ g_{i, l} & = \sum_{r = l}^{m} h_{i, l, r} \\ F_{i, r} & = \sum_{R = 1}^{r} f_{i, R} \\ G_{i, l} & = \sum_{L = l}^{m} g_{i, L} \end{aligned}

于是我们就有：

h_{i, l, r} = P_{l, r} (F_{i - 1, m} - F_{i - 1, l - 1} - G_{i - 1, r + 1})

将 $h$ 代入 $f$ 和 $g$ ，我们有：

\begin{aligned} f_{i, r} & = \sum_{l = 1}^{r} q_{l - 1} q_{m - r} (F_{i - 1, m} - F_{i - 1, l - 1} - G_{i - 1, r + 1}) \\ = q_{m - r} (\sum_{l = 1}^{r} q_{l - 1} (F_{i - 1, m} - F_{i - 1, l - 1}) - G_{i - 1, r + 1} \sum_{l = 1}^{r} q_{l - 1}) \\ g_{i, l} & = \sum_{r = l}^{m} q_{l - 1} q_{m - r} (F_{i - 1, m} - F_{i - 1, l - 1} - G_{i - 1, r + 1}) \\ = q_{l - 1} (\sum_{r = l}^{m} q_{m - r} (F_{i - 1, m} - G_{i - 1, r + 1}) - F_{i - 1, l - 1} \sum_{r = l}^{m} q_{m - r}) \end{aligned}

考虑到最后答案是 $F_{n, m}$ ，我们发现我们可以绕过 $h$ 来求 $F$ 。

最终复杂度 $O (k + n m)$ 。

代码可以看这里。

cpp

#include <map>
#include <set>
#include <stack>
#include <ctime>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <vector>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <fstream>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
namespace pufanyi {
 
    inline char gc() {
        static const int L = 233333;
        static char sxd[L], *sss = sxd, *ttt = sxd;
        if (sss == ttt) {
            ttt = (sss = sxd) + fread(sxd, 1, L, stdin);
            if (sss == ttt) {
                return EOF;
            }
        }
        return *sss++;
    }
 
#ifndef _AT_HOME
#define dd c = gc()
#else
#define dd c = getchar()
#endif
    inline char readalpha() {
        char dd;
        for (; !isalpha(c); dd);
        return c;
    }
 
    inline char readchar() {
        char dd;
        for (; c == ' '; dd);
        return c;
    }
 
    template <class T>
    inline bool read(T& x) {
        bool flg = false;
        char dd;
        x = 0;
        for (; !isdigit(c); dd) {
            if (c == '-') {
                flg = true;
            } else if(c == EOF) {
                return false;
            }
        }
        for (; isdigit(c); dd) {
            x = (x << 1) + (x << 3) + (c ^ 48);
        }
        if (flg) {
            x = -x;
        }
        return true;
    }
#undef dd
 
    template <class T>
    inline void write(T x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        if (x < 10) {
            putchar(x | 48);
            return;
        }
        write(x / 10);
        putchar((x % 10) | 48);
    }
 
    template <class T>
    inline void writesp(T x) {
        write(x);
        putchar(' ');
    }
 
    template <class T>
    inline void writeln(T x) {
        write(x);
        puts("");
    }
 
    typedef long long LL;
 
    const int maxn = 1505;
    const int maxk = 100005;
    const int mod = 1000000007;
 
    inline void add(int& x, int y) {
        x += y;
        if (x >= mod) {
            x -= mod;
        } else if (x < 0) {
            x += mod;
        }
    }
 
    inline int plus(int x, int y) {
        x += y;
        if (x >= mod) {
            x -= mod;
        } else if (x < 0) {
            x += mod;
        }
        return x;
    }
 
    inline int ksm(int a, int b) {
        int ans = 1;
        for (; b; b >>= 1, a = (LL) a * a % mod) {
            if (b & 1) {
                ans = (LL) ans * a % mod;
            }
        }
        return ans;
    }
 
    int n, m, p, k;
    int fac[maxk];
    int inv[maxk];
    int pp[maxk];
    int ppp[maxk];
    int q[maxk];
    int f[maxn];
    int g[maxn];
    int F[maxn];
    int G[maxn];
 
    inline int C(int n, int m) {
        if (n < m) {
            return 0;
        } else {
            return (LL) fac[n] * inv[m] % mod * inv[n - m] % mod;
        }
    }
 
    inline int Main() {
        int a, b;
        read(n), read(m);
        read(a), read(b);
        p = (LL) a * ksm(b, mod - 2) % mod;
        int PP = (mod + 1 - p) % mod;
        read(k);
        fac[0] = 1, pp[0] = 1, ppp[0] = 1;
        for (int i = 1; i <= k; ++i) {
            pp[i] = (LL) pp[i - 1] * p % mod;
            ppp[i] = (LL) ppp[i - 1] * PP % mod;
            fac[i] = (LL) fac[i - 1] * i % mod;
        }
        inv[k] = ksm(fac[k], mod - 2);
        for (int i = k - 1; ~i; --i) {
            inv[i] = (LL) inv[i + 1] * (i + 1) % mod;
        }
        for (int i = 0; i <= m; ++i) {
            q[i] = (LL) C(k, i) * pp[i] % mod * ppp[k - i] % mod;
        }
        f[m] = g[1] = F[m] = G[1] = 1;
        for (int i = 1; i <= n; ++i) {
            int s1 = 0, s2 = 0;
            for (int r = 1; r <= m; ++r) {
                add(s1, (LL) q[r - 1] * (F[m] - F[r - 1]) % mod);
                add(s2, q[r - 1]);
                f[r] = 0;
                add(f[r], s1);
                add(f[r], - (LL) G[r + 1] * s2 % mod);
                f[r] = (LL) f[r] * q[m - r] % mod;
            }
            s1 = 0, s2 = 0;
            for (int l = m; l; --l) {
                add(s1, (LL) q[m - l] * (F[m] - G[l + 1]) % mod);
                add(s2, q[m - l]);
                g[l] = 0;
                add(g[l], s1);
                add(g[l], - (LL) F[l - 1] * s2 % mod);
                g[l] = (LL) g[l] * q[l - 1] % mod;
            }
            for (int r = 1; r <= m; ++r) {
                F[r] = plus(F[r - 1], f[r]);
            }
            for (int l = m; l; --l) {
                G[l] = plus(G[l + 1], g[l]);
            }
        }
        writeln(F[m]);
        return 0;
    }
 
}
 
int main() {
    return pufanyi::Main();
}

Cite this post