| 题目名称 | 782. [SOJ 1141] 猴子的争斗 |
|---|---|
| 输入输出 | merge.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-04-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：23， 提交：28， 通过率：82.14% | ||||
 Ezoi_XY |
100 | 0.001 s | 0.17 MiB | Pascal |
 苏轼 |
100 | 0.001 s | 0.17 MiB | Pascal |
 0-0 |
100 | 0.001 s | 0.17 MiB | Pascal |
 CAX_CPG |
100 | 0.002 s | 0.17 MiB | Pascal |
 QhelDIV |
100 | 0.002 s | 0.27 MiB | C++ |
 神利·代目 |
100 | 0.002 s | 0.29 MiB | C++ |
 ZXCVBNM_1 |
100 | 0.002 s | 0.31 MiB | C++ |
 ミント |
100 | 0.002 s | 0.31 MiB | C++ |
 fanzeyi |
100 | 0.003 s | 0.24 MiB | C |
|
fanzeyi |
100 | 0.003 s | 0.24 MiB | C |
| 本题关联比赛 | |||
| 20120419s | |||
| 关于 猴子的争斗 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Ezoi_XY :
ORZORZORZORZORZ  sqyon
2014-10-09 10:49
2楼
| ||||
|
求生成树的生成方法数（就是生成树的个数*生成树边数全排列）
这题关键在于有个公式———— n阶完全图的生成树个数是 n^(n-2) ; A（n-1，n-1）* n^(n-2) ; | ||||
【问题描述】
从前，在一个森林里有N只好斗的猴子。开始，它们互不认识。互不认识的猴子间是无法避免争斗的，而且争斗只会发生在两只互不认识的猴子间。决斗结束后，这两只猴子和它们各自的朋友们通过这场决斗相互间都认识了，争斗便不会再在这一大群猴子中的任意两只之间发生。
由于决斗是比较激烈的，所以同一时间内不会有两场决斗同时发生。经过N-1次决斗后，这N只猴子间相互都认识了，问有多少种可能的决斗过程。例如N=3，有6种不同的过程：12～13，12～23，13～12，13～32，23～21，23～3l。
【输入】
输入格式(输入文件名merge．in)
文件里只有一个整数N(2≤N≤1000)。
【输出】
输出格式(输出文件名merge．out)、
输出一个整数，为可能的过程的总数除以10007的余数。
【输入输出样例】
输入(merge．in)
4
输出(merge．out)
96