小猴打架 bzoj-1430
题目大意：题目链接。
注释：略。
想法：
我们发现打架的情况就是一棵树。
我们只需要把确定树的形态然后乘以$(n-1)!$表示生成这棵树时边的顺序。
一共$n$个节点我们发现数的形态一共有$n^{n-2}$种。
所以答案就是$n^{n-2}\cdot (n-1)!$。
Code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#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$序列还是很好理解的。