CF708E Student’s Camp 题解

CF708E Student's Camp

题意

• 有一个 $(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;
}