BZOJ1430: 小猴打架

1430: 小猴打架

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 328  Solved: 234
[Submit][Status]

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

题解：

水题。。。

n个点不同形态的生成数有n^(n-2)个，然后打架过程还分先后相当于全排列

所以 ans=n^(n-2) * (n-1)!

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 500+100

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 9999991

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     ll n=read(),ans=;

     for1(i,n-)ans=(ans*n)%mod;

     for1(i,n-)ans=(ans*i)%mod;

     printf("%lld\n",ans);

     return ;

 }