题意

现在有一个 $(n + 2) \times m$ 的网格。会吹 $k$ 次风，每吹一次风，对于除了第一行和最后一行，每一行最左边和最右边的格子，有 $p = \frac{a}{b}$ 的概率会被吹落，这个格子消失。求吹完 $k$ 次风之后，网格仍然连通的概率。

$1 \le n,m \le 1.5 \times 10^3,1 \le k \le 10^5$。

分析

这题一看就很 dp。考虑设 $f_{i,l,r}$ 表示前 $i$ 行仍然联通，第 $i$ 行只剩下了 $[l,r]$ 的格子。因为如果网格不连通，一定是上下不连通，不会出现左右不连通的情况。

首先考虑设 $D(i)$ 表示吹了 $k$ 次风，有 $i$ 次成功的概率。这就是 $D(i) = \begin{pmatrix}k\\i\end{pmatrix}p^i(1-p)^{k-i}$。

方程转移如下。

$$f_{i,l,r} = D(l-1)D(m-r)\sum_{[l’,r’]\cap[l,r]\not=\emptyset } f_{i-1,l’,r’}$$

但是这样子时间复杂度就是 $O(nm^4)$ 的，状态是 $O(nm^2)$ 的，一定是要优化的。

上面的转移本质上就是我们希望两个区间有交集。正难则反，我们考虑求没有交集的概率，然后用总的减去。

$$f_{i,l,r} = D(l-1)D(m-r)(\sum_{1\le l’\le r’\le m} f_{i-1,l’,r’} - \sum_{1\le l’ \le r’ < l} f_{i-1,l’,r’} - \sum_{r<l’\le r’\le m} f_{i-1,l’,r’})$$

这个式子就可以前缀和处理了。设 $S_{i}=\sum_{1\le l\le r\le m} f_{i,l,r}$，$R_{i,j}=\sum_{1\le l\le r\le j} f_{i,l,r}$，$L_{i,j}=\sum_{j\le l\le r\le m} f_{i,l,r}$。我们就可以轻松 $O(nm^2)$ 求出答案了。

接下来我们要处理状态数的问题。我们发现所有状态中，只有 $f$ 是 $O(nm^2)$ 的，其余的都是 $O(nm)$ 的。我们可以考虑只维护前缀和数组。

首先，$L,R$ 数组是几乎一样的，因为左右是完全一样的，所以 $L_{i,j}=R_{i,m-j+1}$。

其次，我们想找到一种 $O(m)$ 快速得到 $R_{i,j}$ 的方法。我们定义 $s_{i,r} = \sum_{l=1}^r f_{i,l,r}$。这样子，$R$ 就可以用 $R_{i,j} = \sum_{k=1}^k s_{i,k}$ 的出了。

因为我们不能求出 $f_{i,l,r}$，我们考虑直接求出 $s_{i,r}$。把 $f_{i,l,r}$ 的式子直接带入 $s_{i,r}$ 的式子。

$$s_{i,r}=\sum_{l=1}^r D(l-1)D(m-r)(S_{i-1}-R_{i-1,l-1}-R_{i-1,m-r})$$
$$=D(m-r)[(S_{i-1}-R_{i-1,m-r})\sum_{j=0}^{r-1} D(j)-\sum_{j=1}^{r-1} D(j)R_{i-1,j}]$$

于是我们只要快速求出 $\sum_{j=0}^x D(j)$ 和 $\sum_{j=1}^x D(j)R_{i-1,j}$ 即可。这两个都可以前缀和。我们可以设 $F(i) = \sum_{j=0}^i D(j),sp_{i,j} = \sum_{k=1}^j D(k)R_{i,k}$。这个转移就可以 $O(nm)$ 实现了。

最后答案就是 $S_n$。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 1505
#define K 100005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
const int P = 1e9 + 7;
int n, m, p, k, D[N], F[N], ans, R[N][N], S[N], sp[N][N], s[N][N], fact[K], invf[K];
il int ksm(int x, int r){
    int ans = 1;
    for (; r; x = 1ll * x * x % P, r >>= 1) if (r & 1) ans = 1ll * ans * x % P;
    return ans;
}
il int C(int n, int m){return 1ll * fact[n] * invf[m] % P * invf[n - m] % P;}
int main(){
    n = rd(), m = rd(), p = 1ll * rd() * ksm(rd(), P - 2) % P, k = rd(), fact[0] = 1;
    for (int i = 1; i <= max(max(n, m), k); i++) fact[i] = 1ll * fact[i - 1] * i % P;
    invf[max(max(n, m), k)] = ksm(fact[max(max(n, m), k)], P - 2); 
    for (int i = max(max(n, m), k) - 1; i >= 0; i--) invf[i] = 1ll * invf[i + 1] * (i + 1) % P; 
    // 预处理阶乘逆元 
    for (int i = 0; i <= min(m, k); i++) D[i] = 1ll * C(k, i) * ksm(p, i) % P * ksm(P + 1 - p, k - i) % P;
    F[0] = D[0];
    for (int i = 1; i <= m; i++) F[i] = (F[i - 1] + D[i]) % P;
    // 预处理 D 和 F 
    S[0] = R[0][m] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            int t1 = 1ll * (S[i - 1] - R[i - 1][m - j] + P) % P * F[j - 1] % P, t2 = sp[i - 1][j - 1];
            s[i][j] = 1ll * D[m - j] * (t1 - t2 + P) % P;
        }
        for (int j = 1; j <= m; j++) R[i][j] = (R[i][j - 1] + s[i][j]) % P;
        for (int j = 1; j <= m; j++) sp[i][j] = (sp[i][j - 1] + 1ll * D[j] * R[i][j] % P) % P;
        S[i] = R[i][m];
    }
    printf ("%d\n", S[n]);
    return 0;
}