over 2 years ago

前言

这道题的思路值得借鉴。

题意

有个的矩阵,在每一天,行每一行有的概率最左边的格子消失,同时也有的概率最右边的格子消失,询问你在天后,整个矩阵还联通的概率。

分析

首先我们可以求出表示在天中消失个格子的概率,很显然:

然后题意告诉我们因为第一行和最后一行不能消失,因此要维护个从上到下联通的的东西。
最简单的就是记录表示第行没消失的一段是的概率,然后这个转移方程是:

也就是说总的概率减去与其无交的概率,利用前缀和优化可以做到
接下来就是这道题精华的地方,我们将状态简化成
因为有对称性,将的第二维定为左端点和右端点是没有区别的。
那么转移方程就是():

,那么原式可以化成:

最后求个和就好了,时间复杂度
E.cpp

← ECR 16 F(经典字符串题)
 
comments powered by Disqus