BZOJ 4766 文艺计算姬


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4766

题意:求一个两边点数分别为 n,m 的完全二分图生成树个数,答案对 p 取模


先放结论 

$$ans=n^{m-1}*m^{n-1}$$

可以打表找一找... 蒟蒻尝试用 prufer 编码证一下

首先考虑 prufer 编码的构建过程,最终生成一个 n-2 的序列后一定剩下两个有边相连的点,那么这两个点一定分别属于 A 集和 B 集,那么其它每个点都被删除一次,删除时会向 prufer 序列中加入一个和删除点有边相连的点,那么这个点一定属于另一个集合,所以 A 集合点被加入 m-1 次,B 集合加入 n-1 次.... 换句话说,我们得到的编码是一个由 m-1 个 A 集合点和 n-1 个 B 集合点构成的序列...

 

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 4766 文艺计算姬


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,