题解 CF708E 【Student's Camp】
pufanyi
·
·
题解
一个简单的想法就是我们令 h_{i,l,r} 表示 k 天后第 i 行还剩下 [l,r]，前 i 行联通的概率。P_{l,r} 表示单独一行只剩 [l,r] 的概率。
首先我们有：
h_{i,l,r}=P_{l,r}\sum_{[l,r]\cap[l',r']\not=\emptyset}h_{i-1,l',r'}
接下来我们考虑 P_{l,r}，我们令 q_{i}=\binom{k}{i}p^i(1-p)^{k-i}，不难发现：
P_{l,r}=q_{l-1}q_{m-r}
然后我们令 f_{i,r} 表示右端点为 r 的所有 h 之和，同理 g_{i,l} 表示以左端点为 l 的所有 h 之和，再令 F_{i,r} 表示右端点小于等于 r 的所有 h 之和，同理 G_{i,l} 表示以左端点大于等于 l 的所有 h 之和。
具体地：
\begin{aligned}
f_{i,r}&=\sum_{l=1}^rh_{i,l,r}\\
g_{i,l}&=\sum_{r=l}^mh_{i,l,r}\\
F_{i,r}&=\sum_{R=1}^rf_{i,R}\\
G_{i,l}&=\sum_{L=l}^mg_{i,L}
\end{aligned}
于是我们就有：
h_{i,l,r}=P_{l,r}\left(F_{i-1,m}-F_{i-1,l-1}-G_{i-1,r+1}\right)
将 h 代入 f 和 g，我们有：
\begin{aligned}
f_{i,r}&=\sum_{l=1}^rq_{l-1}q_{m-r}\left(F_{i-1,m}-F_{i-1,l-1}-G_{i-1,r+1}\right)\\
&=q_{m-r}\left(\sum_{l=1}^rq_{l-1}\left(F_{i-1,m}-F_{i-1,l-1}\right)-G_{i-1,r+1}\sum_{l=1}^rq_{l-1}\right)\\
g_{i,l}&=\sum_{r=l}^mq_{l-1}q_{m-r}\left(F_{i-1,m}-F_{i-1,l-1}-G_{i-1,r+1}\right)\\
&=q_{l-1}\left(\sum_{r=l}^mq_{m-r}\left(F_{i-1,m}-G_{i-1,r+1}\right)-F_{i-1,l-1}\sum_{r=l}^mq_{m-r}\right)
\end{aligned}
考虑到最后答案是 F_{n,m}，我们发现我们可以绕过 h 来求 F。
最终复杂度 \mathcal{O}(k+nm)。