矩阵树定理

撅震树腚里

计算一个图的生成树个数。

设图的邻接矩阵是 \(G\)（\(G_{i,j}\) 就是 \(i,j\) 之间边的条数），度数矩阵 \(D\) (除了 \((i,i)\) 位置是度数其他均为0)，设 \(M=D-G\)，则有该图的生成树数量即为 \(M\) 去掉第 \(i\) 行 \(i\) 列（\(i\) 任意）形成的行列式的值。

行列式求值就是高斯消元消成上三角矩阵。消元过程中，交换两行答案取相反数，一行整体减去另一行倍数不变，某行整体乘 \(x\)，答案也乘 \(x\)。最后的答案就是消元过程中的系数乘上主对角线的乘积。

例：LgP4336。容斥+矩阵树定理。设 \(f(S)\) 是只考虑集合 \(S\) 中公司的边形成的生成树数量，答案显然就是一个简单容斥：\(\sum_S (-1)^{n-1-|S|}f(S)\)。复杂度 \(O(2^{n-1} n^3)\)。