题目二十一：猴子的争斗
【问题描述】
从前在一个森林里，有N只好斗的猴子。一开始，他们互不认识。互不认识的猴子间是无法避免争斗的，而且争斗只会发生在两只互不认识的猴子间。决斗结束后，这两只猴子和他们各自的朋友们通过这场决斗相互间都认识了，争斗便不会再发生在这一大群猴子中的任两只。由于争斗是比较激烈的，所以同一时间内不会有两场决斗一起发生。经过N-1次决斗后，这N只猴子间相互都认识了，现在问有多少种可能的决斗过程。例如N=3，有6种不同的过程：12->13，12->23，13->12，13->32，23->21， 23->31。
【要求】
【数据输入】文件里只有一个整数N(2≤N≤1000)。
【数据输出】输出一个整数，为可能的过程的总数除以10007的余数。
【样例输入】
4
【样例输出】
96
新手求教，不怕代码长，只求能看懂，跪谢各位大神

好像很复杂的样子，看不大懂

验证当n=3时~当n=2时共有1种情况~三只猴任意抽取两只决斗共有三种情况~然后剩下一只猴子与可以任意选择两只猴子决斗~顾当n=3时有六种情况~

三只互不相识的猴子决斗共有6种~三只互不相识的决斗后再和第四只决斗可以派出任意一只猴子和第四只猴子决斗~这时有6*3=18种~而4只猴子抽取任意三只本来共有4种情况~所以当n=4时共有6*3*4=18*4=72种情况~

但答案是96种~难道推理出现了什么问题么？~

感觉数要%10007~这个提示后者的值要借用前者来解应该没错~但我推出当n=4时是72而不是答案96就不好再继续推下去了~

知道出错原因了~原来少考虑了四只猴子两两决斗再一起决斗这种情况~四只猴子抽取不同的两只猴子决斗有6种情况~然后每一只猴子可以和另外两只猴子决斗~共有6*4=24种~顾n=4时共有72+24=96种~

//推了这么多还是错了~还是忽略~

接下来~重申当n=4时~需要考虑两种情况~即(3,1)和(2,2)
(3,1)里面有6*3*4=72种情况~(2,2)共有3*2*4=24种情况~n=4共有96种情况~

当n=5时~只需要考虑(4,1)和(3,2)两种情况~(2,2,1)的情况已经包含在(4,1)和(3,2)里面~

当为n并n>2时~要考虑(n-1,1)……(n-2,2)共有n/2种情况~
顾只需求出(Na,Nb)的值即可~
(Na,Nb)=Na*Nb*Cn_a*a*b
N1=1
N2=1
N3=N(2,1)=1*1*3*2*1=6~
N4=N(3,1)+N(2,2)=6*1*4*3*1+1*1*6*2*2=72+24=96~
N5=N(4,1)+N(3,2)=96*1*5*4*1+6*1*10*3*2=1920+360=2280~
但感觉可能会有漏洞~N(2,2,1)是否包含在上述情况里面得要再推敲一下~
有时间补充代码~

更正~N(a,b)算法有问题~当n=5时应该为2640种~

[此贴子已经被作者于2017-3-1 09:50编辑过]

不考虑10007的余数，公式为：s=(n-1)!*n^(n-2)，这好像是竞赛试题，公式已经满天飞了。
n=4
s=(4-1)!*4^(4-2)=(1*2*3)*(4*4)=96

n=5
s=(5-1)!*5^(5-2)=(1*2*3*4)*(5*5*5)=3000

好想撤回上贴写了那么多还是错的~~

[此贴子已经被作者于2017-3-1 09:49编辑过]

刚刚再推敲了一下当n=5的情况~昨晚思考还是少考虑了一种情况~补充后是2640+360=3000确实是3000种~