Posts tagged with Cayley


完全二分图的生成树计数问题。 这里是作为找规律的题目出现的…… 对于这张图的一边 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)…