在搜最小生成树计数的题目的时候不小心发现了一个有趣的东西
完全图的最小生成树计数问题……题解说需要01字典树，不是很会，先放一放
然后就找到了这个资料 Prüfer编码与Cayley公式
简单说完全图的生成树数量为 ( n^{n-2} )
这个运用矩阵树也可以计算的
题意：
n只猴子打架，两只猴子打架后就会成为好朋友，就不会打架，朋友关系可传递，问打架的序列方案数。
思路：
n个点的生成树数量为 ( n^{n-2} ) ，顺序为 (n-1)!
AC Code
#include <cstdio>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
const int mod = 9999991;
int n;
long long ans = 1;
int main()
{
scanf("%d", &n);
range(i, 1, n - 2) ans = ans * n % mod;
range(i, 1, n - 1) ans = ans * i % mod;
printf("%lld", ans);
return 0;
}