[二分图+矩阵树定理]LOJ6044(雅礼集训 2017 Day8)【共】题解
题目概述有 $n$ 个点的树，$1$ 为根，每个节点的深度定义为到根的点数。求深度为奇数的点恰好为 $K$ 的树的个数。解题报告emm……我们把树按照深度奇偶分开，就变成了一个二分图，两边点数为...
[矩阵树定理]BZOJ4894【天赋】题解
题目概述有 $n$ 个技能，每个技能有一些前置技能，现在 $1$ 技能已学习，求学完所有技能的方案数。解题报告矩阵树定理求有向图中外向树和内向树的个数：外向树：边从父亲到儿子的有向树度数矩阵为每...
[矩阵树定理]BZOJ4766【文艺计算姬】题解
题目概述求二分图 $K_{n,m}$ 的生成树个数。解题报告我骗我自己：$A+B=d(dA+dB)$ ，导致我做不出来。二分图的基尔霍夫矩阵的一个主子式长这样（上面 $n$ 行，下面 $m-1$...
[矩阵树定理]BZOJ4031(HEOI2015)【小Z的房间】题解
题目概述有 $n\times m$ 的网格，每个网格是房间或者柱子，周围都有墙，问打破墙使得房间连成一棵树的方案数。解题报告矩阵树裸题，问题是行列式取模，因为不是质数所以不能逆元。那么辗转相除就...
[矩阵树定理]SPOJ(HIGH)【Highways】题解
题目概述给出一张无向图，求生成树个数。解题报告大佬传送门：*ZJ，Candy?。矩阵树定理裸题，先来讲（瞎扯）一波行列式：行列式定义式：$Det(A)=\sum_{P}(-1)^{\tau(P)...
