题解 CF708E 【Student's Camp】
xht
2020-03-11 21:48:04
> [CF708E Student's Camp](https://codeforces.com/contest/708/problem/E)
## 题意
- 有一个 $(n+2) \times m$ 的网格。
- 除了第一行和最后一行，其他每一行每一天最左边和最右边的格子都有 $p$ 的概率消失。
- 求 $k$ 天后，网格始终保持连通的概率。
- $n,m \le 1.5 \times 10^3$，$k \le 10^5$，答案对 $10^9+7$ 取模。
## 题解
网格始终保持连通，等价于 $k$ 天后任意相邻两行剩下的区间有交。
考虑区间 dp，设 $f_{i,l,r}$ 表示前 $i$ 行连通且第 $i$ 行剩下的区间为 $[l,r]$ 的概率。
初始条件为 $f_{0,1,m} = 1$，转移：
$$f_{i,l,r} = p_{l,r}\sum_{[l^\prime, r^\prime] \cap [l,r] \ne \varnothing} f_{i-1,l^\prime,r^\prime}$$
其中 $p_{l,r}$ 表示 $k$ 天后剩下 $[l,r]$ 的概率，有 $p_{l,r} = p_{l-1} \times p_{m-r}$，$p_i = \binom{k}{i} p^i (1-p)^{k-i}$。
直接做是 $\mathcal O(nm^2)$ 的，显然无法接受。
设 $fr_{i,r} = \sum_{l\le r} f_{i,l,r}$，$sr_{i,j} = \sum_{r \le j} fr_{i,r}$。
同理设 $fl_{i,l} = \sum_{l \le r} f_{i,l,r}$，$sl_{i,j} = \sum_{l \ge j} fl_{i,l}$。
由于左右完全对称，因此 $fl_{i,j} = fr_{i,m+1-j}$，$sl_{i,j} = sr_{i,m+1-j}$。
则有：
$$\begin{aligned}f_{i,l,r}&= p_{l,r}\sum_{[l^\prime, r^\prime] \cap [l,r] \ne \varnothing} f_{i-1,l^\prime,r^\prime} \\\\&= p_{l,r}(sr_{i-1,m} - sr_{i-1,l-1} - sl_{i-1,r+1}) \\\\&= p_{l,r}(sr_{i-1,m} - sr_{i-1,l-1} - sr_{i-1,m-r})\end{aligned}$$
于是我们只需要计算 $fr_{i,j}$，然后前缀和求出 $sr_{i,j}$ 即可。
又有：
$$\begin{aligned}fr_{i,r}&= \sum_{l\le r} f_{i,l,r} \\\\&= \sum_{l\le r} p_{l,r}(sr_{i-1,m} - sr_{i-1,l-1} - sr_{i-1,m-r})\\\\&= \left((sr_{i-1,m}-sr_{i-1,m-r})p_{m-r}\sum_{l\le r} p_{l-1}\right) - \left(p_{m-r} \sum_{l\le r} p_{l-1} sr_{i-1,l-1}\right) \\\\&= p_{m-r}\left((sr_{i-1,m}-sr_{i-1,m-r})\sum_{l\le r} p_{l-1} - \sum_{l\le r} p_{l-1} sr_{i-1,l-1}\right)\end{aligned}$$
那么我们可以预处理 $q_r = \sum_{l\le r}p_{l-1}$，$g_{i,r} = \sum_{l \le r} p_{l-1}sr_{i,l-1}$，然后 $\mathcal O(nm)$ 计算出所有的 $fr_{i,j},sr_{i,j}$，从而计算出最终的答案，也就是 $sr_{n,m}$。
## 代码
```cpp
const int N = 1.5e3 + 7;
int n, m, k, a, b;
modint x, p[N], q[N], f[N][N], s[N][N], g[N][N];
inline modint binom(int i, int j) {
modint a = 1, b = 1;
for (int k = 1; k <= j; k++) a *= i + 1 - k, b *= k;
return a / b;
}
int main() {
rd(n), rd(m), rd(a), rd(b), rd(k), x = (modint)a / b;
for (int i = 0; i <= min(m, k); i++)
p[i] = binom(k, i) * (x ^ i) * ((1 - x) ^ (k - i));
for (int i = 1; i <= m; i++) q[i] = q[i-1] + p[i-1];
f[0][m] = s[0][m] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
f[i][j] = p[m-j] * ((s[i-1][m] - s[i-1][m-j]) * q[j] - g[i-1][j]),
s[i][j] = s[i][j-1] + f[i][j],
g[i][j] = g[i][j-1] + p[j-1] * s[i][j-1];
print(s[n][m]);
return 0;
}
```