题意
n个点问有多少种有顺序的连接方法把这些点连成一棵树。
(n<=106)
题解
了解有关prufer编码与Cayley定理的知识。
可知带标号的无根树有nn-2种。然后n-1条边有(n-1)!的先后连接顺序。
所以答案为nn-2(n-1)!
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int mod=;
long long ans,n;
int main(){
scanf("%lld",&n);
ans=;
for(long long i=;i<=n-;i++){
ans*=n;
ans%=mod;
}
for(long long i=;i<=n-;i++){
ans*=i;
ans%=mod;
}
printf("%lld",ans);
return ;
}