1430: 小猴打架

1430: 小猴打架

Time Limit: 5 Sec   Memory Limit: 162 MB Submit: 586   Solved: 421 [ Submit][ Status][ Discuss]

Description

一开始森林里面有N只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过N-1次打架之后，整个森林的小猴都会成为好朋友。 现在的问题是，总共有多少种不同的打架过程。 比如当N=3时，就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的打架过程。

Input

一个整数N。

Output

一行，方案数mod 9999991。

Sample Input

4

Sample Output

96

HINT

50%的数据N<=10^3。 100%的数据N<=10^6。

Source

[ Submit][ Status][ Discuss] 考虑一棵无根树的prufer序列 由于本题生成树的度数没有限制，所以每个点出现的次数随意 那么答案就是n^(n-2) 然后边的生成顺序不同也是不同的方案，所以再乘上(n-1)! 综上，Ans = (n-1)!*n^(n-2) #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #include<bitset> #include<ext/pb_ds/priority_queue.hpp> using namespace std; typedef long long LL; const LL mo = 9999991; int n,fac = 1; int Mul(const LL &x,const LL &y) {return x * y % mo;} int ksm(int x,int y) { int ret = 1; for (; y; y >>= 1) { if (y & 1) ret = Mul(ret,x); x = Mul(x,x); } return ret; } int main() { cin >> n; for (int i = 1; i < n; i++) fac = Mul(fac,i); cout << Mul(fac,ksm(n,n - 2)) << endl; return 0; }