CF446D DZY Loves Games 题解

$k$ 很大，因此考虑矩阵快速幂。考虑找出图 $G$ 的一个导出子图，对于每一对 $(x,y)$，若 $x,y$ 都为陷阱且有边相连，则 $x,y$ 以及连接她们的一条无向边都在这个导出子图中。

现在只需要求出图中两两不经过其他导出子图结点（即陷阱点）而到达的概率。通过她我们就可以直接矩阵快速幂快速计算出答案。问题在于如何求出这个概率，这里我们记 $f_{i,j}$ 表示从 $i$ 到 $j$ 的概率（$j$ 为陷阱点）。那么很显然有初始条件 $\forall i,f_{i,i}=1$。否则若 $i$ 为陷阱，则显然 $f_{i,j}=0$。否则考虑转移，设 $o$ 为 $i$ 点的所有出边，则 $f_{i,j}=\frac{\sum\limits_o f_{o,j}}{\deg(i)}+1$。

观察到 dp 式的第二维固定，因此考虑枚举第二维 $j$。但是此时 dp 式带环，因此可以用高斯消元转移，时间复杂度为 $O(n^3t)$ 会爆炸（$t$ 是图中陷阱点的数目，$t\le 100$）。考虑优化。此时发现系数矩阵相同，因此考虑扩展高斯消元的矩阵，把 $t$ 次都放在矩阵右侧一起做高斯消元。此时时间复杂度优化到 $O(t^3\log k+n^3)$，可以通过。