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

对于相邻的房间连一条无向边。 我们考虑选择一条边就表示打破一面墙。 那么题目要求两个房间**只有**一条道路，等价于我们最后选择的图是一颗树。 那么题目就是生成树计数。 用 _Matirx-Tree_ 定理即可。 注意模数不是质数，所以高斯消元时要注意。 时间复杂度 $O(n^3m^3log(nm))$ 空间复杂度 $O(n^2m^2)$ 代码就不放了。