BZOJ 4031 [HEOI2015] 小 Z 的房间

发布于 2017-07-05  180 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4031

题意:一个包含 n*m 个格子的网格图,每个格子是一个房间或者是一个柱子。在一开始的时候,相邻的格子之间都有墙隔着。你想要打通一些相邻房间的墙,使得所有房间能够互相到达。在此过程中,你不能把房子给打穿,或者打通柱子(以及柱子旁边的墙)。同时你希望任意两个房间之间都只有一条通路。现在,你希望统计一共有多少种可行的方案。答案对 109 取模。


显然建模后求生成树个数即可,

度数矩阵 :D[x][x] 表示点 x 的度数,其它元素为 0
邻接矩阵 :A[x][y] 代表 xy 是否有边。有边则为 1,否则为 0.

基尔霍夫矩阵:C=D-A.

Matrix-Tree 定理 :对于一个基尔霍夫矩阵,随意去掉第 r 行 和第 r 列 (\(r\in [1,n]\)),留下的这个矩阵的行列式的 绝对值 ,就是生成树的个数。

对于质数模意义下的矩阵行列式计算,显然直接处理逆元即可,那么一般的合数呢?如此题

高精度分数?中国剩余定理?都不是很优雅的解决方案

根据代数知识,矩阵的任意一行减去另一行的倍数,行列式不变。交换两行,行列式变负。所以我们可以用一种类似辗转相除法的姿势,不断地减,交换,直到被消元行被减到 0 为止,时间复杂度是 log 级别的,且在模意义下的实现是很方便的。

 

 


一个非常弱的准退役OIER