BZOJ 1430 小猴打架

题目大意

求N个点的最小生成树的排列个数。

根据一个经典公式和证明,一个完全图有$n^{n-2}$棵生成树。每棵生成树都有$(n-1)!$的排列，所以最终答案就是$n^{n-2} \times (n-1)!$

#include <cstdio>
#define MO 9999991
long long n,ans=1;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n-2;++i) ans=(ans*n)%MO;
	for(int i=1;i<=n-1;++i) ans=(ans*i)%MO;
	printf("%lld\n",ans);
	return 0;
}