Posts tagged with Maths


完全二分图的生成树计数问题。 这里是作为找规律的题目出现的…… 对于这张图的一边 n 个节点,另一边 m 个节点。 其结果为 $$n^{m-1} \times m^{n-1}$$ 因为数据非常大,为 1e18 ,long long 也会爆炸 用到了快速乘,快速幂 题意: 计算完全二分图的生成树数量 思路:…

在搜最小生成树计数的题目的时候不小心发现了一个有趣的东西 51nod 1601 完全图的最小生成树计数问题……题解说需要01字典树,不是很会,先放一放 然后就找到了这个资料 Prüfer编码与Cayley公式 简单说完全图的生成树数量为 ( n^{n-2} ) 这个运用矩阵树也可以计算的 题意: n只猴子打架,两只猴子打架后就会成为好朋友,就不会打架,朋友关系可传递,问打架的序列方案数。 思路: n个点的生成树数量为 ( n^{n-2} ) ,顺序为 (n-1)…

矩阵树定理第二题,用于有取模处理的运算。 中间一直超时,还一位bzoj会卡宏定义……真是石乐志 题意: 给你一个n×m矩阵,矩阵中的’ . ‘表示成一个房间,’ * ‘ 表示柱子,在相邻的房间中可以连边,要求每个房间都相连,求方案数。 思路: 算是比较裸的矩阵树定理应用了,对每一个点,标号,再对相邻都是点的格子建边。 AC Code #include <algorithm>…

早上在学最小生成树计数。 最小生成树算法基于 Matrix-Tree 定理,Matrix-Tree定理是被广泛应用与求生成树计数中。 其具体流程为构造基尔霍夫矩阵,再对其求 n-1 阶行列式即可。 基尔霍夫矩阵 为 其度数矩阵D[G] – 邻接矩阵A[G] 度数矩阵D[G] 满足,当 i≠ j 时,dij=0;当i=…