Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 1430: 小猴打架

题目链接

传送门

Description

一开始森林里面有N只互不相识的小猴子,它们经常打架,但打架的双方都必须不是好朋友。每次打完架后,打架的双方以及它们的好朋友就会互相认识,成为好朋友。经过N-1次打架之后,整个森林的小猴都会成为好朋友。 现在的问题是,总共有多少种不同的打架过程。 比如当N=3时,就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的打架过程。

Input

一个整数N,N<=10^6

Output

一行,方案数mod 9999991。

Sample Input

4

Sample Output

96

想说的话

传说中的不打不相识?!
没事和谐相处不要打架嘛

题解

又是一道结论题
你需要知道prufer编码以及一个叫做Cayley定理的东西
prufer编码不知道的出门右转
Cayley定理说的是什么呢
这个东西在数学上面特别伟大
不过在OI的应用就一点
有n个标志点的树的数目是n^(n-2)
再加上prufer定理我们得到同一棵树有(n-1)!种生成方式
所以最终的答案就是(n-1)!*n^(n-2)

吐槽

我写明明的烦恼写怕了
全用的快速乘快速幂
还开了unsigned long long

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏