题解 P4111 【[HEOI2015]小Z的房间】

对于相邻的房间连一条无向边。

我们考虑选择一条边就表示打破一面墙。

那么题目要求两个房间只有一条道路,等价于我们最后选择的图是一颗树。

那么题目就是生成树计数。

Matirx-Tree 定理即可。

注意模数不是质数,所以高斯消元时要注意。

时间复杂度 $O(n^3m^3log(nm))$ 空间复杂度 $O(n^2m^2)$

代码就不放了。


发表于 2018-02-08 12:30:27 in 题解