题解 CF708E 【Student's Camp】

· · 题解

如果题解页面公式崩坏，请 在博客中查看。

首先转化题意。题目中已经限定了最高和最低一行的方块不会被吹走，所以整个建筑「不连通」只可能是被「上下劈开」，不可能是被「左右劈开」。也就是说，整个建筑「连通」，当且仅当对于所有相邻的两行，它们最后剩下的方块连通。

考虑 DP。设 f(i,l,r) 表示第 i 行剩下 [l,r] 的方块且建筑不倒的概率。

先考虑某一行剩下 [l,r] 的方块的概率。

设 D(i) 表示 k 次「吹风」中 i 次成功的概率，显然

D(i) = \binom k i p^i(1-p)^{k-i}

可以 O(k) 预处理求出所有的 D(i)。

设 P(l,r)\ (1 \le l \le r \le m) 表示某一行只剩下 [l,r] 的砖块的概率，由于左右两边相互独立，可以得到

P(l,r) = D(l-1) D(m-r)

接下来考虑如何从第 i-1 行转移。

由前面的分析，第 i 行最后剩下的方块所占的区间要和第 i-1 行的区间有交，即

f(i,l,r) = P(l,r) \sum_{[l',r']\cap[l,r] \ne \varnothing} f(i-1,l',r')

边界是 f(0,1,m) = 1，答案即为所有 f(n,l,r) 的和。

这样状态数为 O(nm^2)，转移复杂度 O(m^2)，需要优化。

考虑问题的反面，即 [l,r] 和 [l',r'] 没有交集。容易发现，这只有两种互斥的情况：要么 r' \lt l，要么 l' \gt r。

于是，我们得到：

f(i,l,r) = P(l,r) \left[ \sum_{l' \le r'} f(i-1,l',r') - \sum_{r' \lt l} f(i-1,l',r') - \sum_{l' \gt r} f(i-1,l',r') \right]

发现只要求出三个求和号的部分就能转移了，即

\begin{aligned} F(i) &= \sum_{l \le r} f(i,l,r) \\ L(i,x) &= \sum_{l \le r \lt x} f(i,l,r) \\ R(i,x) &= \sum_{r \ge l \gt x} f(i,l,r) \\ f(i,l,r) &= P(l,r) \Big[ F(i-1) - L(i-1,l) - R(i-1,r) \Big] \end{aligned}

注意其中 F(i) 的意义，它表示前 i 行连通的概率，那么答案就是 F(n)。

细心的同学可能已经发现了，L(i,x) 和 R(i,x) 在转移、形式和结果上都是高度对称的。事实上，把 L(i,x) 左右翻转就可以得到 R(i,x)，即 L(i,x)=R(i,m-x+1)。于是我们只要讨论 L(i,x) 的处理就可以了。

由于 f(i,l,r) 会对所有 x \gt r 的 L(i,x) 产生贡献，我们可以先记 S_L(i,r) 表示所有右端点为 r 的 f(i,l,r) 之和，则对 S_L 计算前缀和即可得到 L，用公式表达就是：

\begin{aligned} S_L(i,r) &= \sum_{l \le r} f(i,l,r) \\ L(i,x) &= \sum_{r \lt x} S_L(i,r) \end{aligned}

同时我们可以发现，所有的 S_L(i,r) 之和就等于 F(i)，这样就把 F(i) 也一并解决了。

接下来考虑如何计算 S_L(i,r)，把 f(i,l,r) 的转移式代入：

\begin{aligned} S_L(i,r) &= \sum_{l \le r} f(i,l,r) \\ &= \sum_{l \le r} P(l,r) \Big[ F(i-1) - L(i-1,l) - R(i-1,r) \Big] \\ &= D(m-r) \sum_{l \le r} D(l-1) \Big[ F(i-1) - L(i-1,l) - R(i-1,r) \Big] \\ &= D(m-r) \left( \Big[ F(i-1)-R(i-1,r) \Big] \sum_{l \le r} D(l-1) - \sum_{l \le r} D(l-1) L(i-1,l) \right) \end{aligned}

到这里思路已经很清晰了，对 D(l-1) 和 D(l-1) L(i-1,l) 做前缀和即可实现 O(1) 转移，最后答案即为 F(n)。边界同样是 f(0,1,m)=1，即 S_L(0,m)=1。

总时间复杂度 O(nm+k)，空间复杂度可以用滚动数组优化至 O(m+k)。