题解：P13004 [GCJ 2022 Finals] Schrödinger and Pavlov

· · 题解

关于现有两篇题解的补充说明。

首先计数转概率，设 p_i 表示 i 号盒子里有猫的概率。如果存在一条有向边 i\to j，容易推出，操作一下盒子 i 的转移形如 \begin{cases} p'_i\gets p_ip_j\\ p'_j\gets p_i+p_j-p_ip_j\end{cases}。

在转移中，我们使用 p_i 和 p_j 相乘刻画二者同时成立，假定了 p_i 和 p_j 之间是独立的。如果 p_i 和 p_j 不独立，相乘是没道理的。我们不能用 \frac{1}{2}\cdot \frac{1}{2} 计算两个焊在一起的硬币同时正面朝上的概率。

当连通块构成一棵内向树时，二者确实独立，因为转移当前这条边前，两侧之间不会有转移。

所以，当连边是基环树时，在环上选一条边钦定它有没有起作用后，剩下的转移便可以正确进行。

理论上只要选的边在环上都是对的，另外一篇题解说只能选第一条，我猜是因为他实现的时候不小心把边选到环外面了。