CF708E

传送门

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)\)。

code

Submission #233808497 - Codeforces