由Prufer编码可以引申出来一个定理：Cayley
内容是不同的n结点标号的树的数量为n^(n-2)
换一种说法就是一棵无根树，当知道结点总数的时候，其最多可能有n^(n-2)种形态
这只是形态而已
对于BZOJ1430这道题
题目的打架关系可以用无根树来描述
除了形态之外，还要考虑打架的顺序，一共(n-1)!种
乘起来即可
1 #include<cstdio> 2 const int mod=9999991; 3 int n; 4 long long ans=1; 5 int main() 6 { 7 scanf("%d",&n); 8 for(int i=1;i<=n-2;i++) 9 ans=(ans*n)%mod; 10 for(int i=1;i<=n-1;i++) 11 ans=(ans*i)%mod; 12 printf("%lld",ans); 13 return 0; 14 }
原文：https://www.cnblogs.com/aininot260/p/9425940.html