描述
一开始森林里面有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}六种不同的打架过程。
题解
问题 $=$ 求出$N$个有标号节点的树的个数 $\times$ 连边的顺序。
因为有 $N - 1$条边， 所以连边的顺序就是 $!(N-1)$。
然后需要考虑的就是$N$个有标号节点的树的个数。
我们首先要介绍prufer数列， 传送门
prufer数列的构造方法 ：找出度数为1 的节点中标号最小的点$x$，将与它相连的节$y$点录入数列， 再删除$x$。
重复上述过程 ， 直到只剩两个点。 这样构造出的数列与树唯一对应。 并且树也唯一对应数列。即数列的个数与树的个数相同。
个数都为$N^{N-2}$
最后的答案就是$N^{N - 2} \times !(N - 1)$
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod = ; ll ans, n; ll fpow(ll a,ll p) {
ll re = ;
for(; p; p >>= , a = a * a % mod) if(p & ) re = re * a % mod;
return re;
} int main()
{
scanf("%lld", &n);
ans = fpow(n, n - );
for(int i = ; i < n; ++i) ans = ans * i % mod;
printf("%lld\n", ans);
}