小猴打架 bzoj-1430

题目大意：题目链接。

注释：略。

---

想法：

我们发现打架的情况就是一棵树。

我们只需要把确定树的形态然后乘以$(n-1)!$表示生成这棵树时边的顺序。

一共$n$个节点我们发现数的形态一共有$n^{n-2}$种。

所以答案就是$n^{n-2}\cdot (n-1)!$。

Code：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define mod 9999991 using namespace std;typedef long long ll;ll qpow(ll x,ll y){	ll ans=1; while(y)	{		if(y&1) (ans*=x)%=mod;		y>>=1;		(x*=x)%=mod;	}	return ans;}int main(){	ll n; cin >> n ;	ll ans=1; for(int i=1;i<=n-1;i++) (ans*=i)%=mod;	printf("%lld\n",qpow(n,n-2)*ans%mod);	return 0;}
        
       
      
     

小结：$prufer$序列还是很好理解的。