BZOJ 4766 文艺计算姬
完全二分图的生成树计数问题。
这里是作为找规律的题目出现的……
对于这张图的一边 n 个节点，另一边 m 个节点。 其结果为
$$n^{m-1} \times m^{n-1}$$
因为数据非常大，为 1e18 ，long long 也会爆炸
用到了快速乘，快速幂
题意：
计算完全二分图的生成树数量
思路：
公式已给。证明无。
……
AC Code
#include
BZOJ 1430 小猴打架
在搜最小生成树计数的题目的时候不小心发现了一个有趣的东西
51nod 1601
完全图的最小生成树计数问题……题解说需要01字典树，不是很会，先放一放
然后就找到了这个资料 Prüfer编码与Cayley公式
简单说完全图的生成树数量为 ( n^{n-2} )
这个运用矩阵树也可以计算的
题意：
n只猴子打架，两只猴子打架后就会成为好朋友，就不会打架，朋友关系可传递，问打架的序列方案数。
思路：
n个点的生成树数量为 ( n^{n-2} ) ，顺序为 (n-1)!
AC Code
#include
BZOJ 4031 小Z的房间
矩阵树定理第二题，用于有取模处理的运算。
中间一直超时，还一位bzoj会卡宏定义……真是石乐志
题意：
给你一个n×m矩阵，矩阵中的’ . ‘表示成一个房间，’ * ‘ 表示柱子，在相邻的房间中可以连边，要求每个房间都相连，求方案数。
思路：
算是比较裸的矩阵树定理应用了，对每一个点，标号，再对相邻都是点的格子建边。
AC Code
#include
SPOJ 104 Highways
早上在学最小生成树计数。
最小生成树算法基于 Matrix-Tree 定理，Matrix-Tree定理是被广泛应用与求生成树计数中。
其具体流程为构造基尔霍夫矩阵，再对其求 n-1 阶行列式即可。
* 基尔霍夫矩阵 为 其度数矩阵D[G] – 邻接矩阵A[G]
* 度数矩阵D[G] 满足，当 i≠ j 时,dij=0；当i=j时，dij等于vi的度数。
* 邻接矩阵A[G] 满足，如果vi、vj之间有边直接相连，则aij=1，否则为0。
不得不说SPOJ的数据之强，一个小问题找了我大半天才找着，SPOJ倒是我想做验证模板的不二之选。
#include