题解：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}$ 计算两个焊在一起的硬币同时正面朝上的概率。

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

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

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