p4981父子， prufer序列->cayley定理
n点无根树的选择方法是n^(n-2)
一个无根树有n个点选作根，
方法数=n^(n-2)*n=n^(n-1)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+9;
ll t,n;
ll qmi(ll a,ll b){
ll res=1;
while(b){
if(b&1) res*=a, res%=mod;
a*=a, a%=mod; b>>=1;
}
return res;
}
int main(){
for(cin>>t;t--;){
cin>>n;
cout<<qmi(n,n-1)<<endl;
}
return 0;
} 
查看1道真题和解析