BZOJ 4766 文艺计算姬

发布于 2017-06-14  147 次阅读


题目链接: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 集合点构成的序列...

 

 


一个非常弱的准退役OIER