BZOJ 1430 小猴打架

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


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

题意:n 只小猴子打架,打完架是好朋友,好朋友不打架,打架 n-1 次大家都是好朋友的方案数...


根据 Cayley 定理:

n 阶完全图的生成树个数为\(n^{n-2}\)

对于这道题,打架的顺序不同是不同的方案,所以乘一个 (n-1)! 即可

prufer 编码好有趣,有机会具体写一写

 


一个非常弱的准退役OIER