description
给定 \(n,m,P,k\)。一个 \(n+2\) 行 \(m\) 列的网格图第 \(2\) 至 \(n+1\) 行每秒每行左右两端的方格都有 \(P\) 的概率消失。求 \(k\) 秒后第一行和最后一行联通（上下左右四个格子联通）的概率。
-
\(n,m\leq 1.5\times10^5\)
-
\(k\leq 10^5\)
solution
由于每行都是一样的，所以可以首先求出 \(c_{l,r}\) 表示 \(k\) 秒后恰剩下 \([l,r]\) 这一段没有消失的概率。根据消失的规则，有表达式：
- \(c_{l,r}=\dbinom{k}{l-1}P^{l-1}(1-P)^{k-(l-1)}\times \dbinom{k}{m-r}P^{m-r}(1-P)^{k-(m-r)}\)
设 \(f_{t,l,r}\) 表示前 \(t\) 行（行号从 0 开始）联通并且第 \(t\) 行还剩 \([l,r]\) 没有删除的概率。设 \(S_t=\sum\limits_{l=1}^m\sum\limits_{r=l}^m f_{t,l,r}\)。考虑上一行填了哪一段，则有转移：
- \(f_{t,l,r}=c_{l,r}\times(S_{t-1}-\sum\limits_{i=1}^{l-1}\sum\limits_{j=i}^{l-1} f_{t-1,i,j}-\sum\limits_{i=r+1}^m\sum\limits_{j=i}^mf_{t-1,i,j})\)
注意，因为两线段相交的条件比较复杂，所以容斥一下，考虑两线段不相交的条件，进而得出上式。
直接转移的时间复杂度是 \(O(nm^4)\)。考虑优化这个 dp。
状态数量已经到达三次方级别，不能接受，所以要先把状态变成两维。
我们设 \(f_{t,r}=\sum\limits_{l=1}^r f_{t,l,r}\) 以及 \(g_{t,l}=\sum\limits_{r=l}^m f_{t,l,r}\) 即原 dp 状态确定左端点或右端点后的后缀和或前缀和。则此时 \(S_{t}=\sum\limits_{r=1}^m f_{t,r}=\sum\limits_{l=1}^m g_{t,l}\)。
以 \(f_{t,r}\) 为例说明如何转移，\(g_{t,l}\) 的转移同理。
考虑把 \(f_{t,r}\) 展开得：
- \(f_{t,r}=\sum\limits_{l=1}^r f_{t,l,r}\)
考虑在知道 \(f_{t-1}\) 和 \(g_{t-1}\) 得情况下计算 \(f_{t,l,r}\)：
- \(f_{t,r}=\sum\limits_{l=1}^r c_{l,r}\times (S_{t-1}-f_{t-1,l-1}-g_{t-1,r+1})\)
单独考虑每一项：
- \(f_{t,r}=(S_{t-1}-g_{t-1,r+1})\sum\limits_{l=1}^r c_{l,r}-\sum\limits_{l=1}^r c_{l,r}f_{t-1,l-1}\)
后一项直接不好处理，但是我们可以根据最开始推的式子把 \(c_{l,r}\) 拆成分别和 \(l,r\) 相关的两部分，分别是 \(L(l)=\dbinom{k}{l-1}P^{l-1}(1-P)^{k-(l-1)}\) 和 \(R(r)=\dbinom{k}{m-r}P^{m-r}(1-P)^{k-(m-r)}\)。
则式子可化为：
- \(f_{t,r}=(S_{t-1}-g_{t-1,r+1})\times R(r)\sum\limits_{l=1}^r L(l)-R(r)\sum\limits_{l=1}^r L(l)f_{t-1,l-1}\)
这样每部分都可以前缀和优化了。
时间复杂度 \(O(nm)\)。