CF708E Student’s Camp 题解
Visits: 256
题意
- 有一个 $(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}$。
代码
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;
}