【BZOJ】【1430】小猴打架

时间:2023-12-24 12:43:49

排列组合

  蛮逗的……

  这题题干描述的就一股浓浓的Kruskal的气息……很容易就想到是求一个n个点的完全图的生成树个数,然后由于有序,再乘一个n-1的排列数(n-1条边的全排列)即(n-1)!

  但是我一下就卡在了 完全图的生成树个数这个地方……怎么也想不出来……后来看了题解,原来这是一个奇葩的结论:【n^(n-2)】

  好吧剩下的就是水了……完全无压力……

  Cayley公式

 /**************************************************************
Problem: 1430
User: Tunix
Language: C++
Result: Accepted
Time:176 ms
Memory:804 kb
****************************************************************/ //BZOJ 1430
#include<cstdio>
typedef long long LL;
int main(){
int n,p=;
LL ans=;
scanf("%d",&n);
for(int i=;i<=n-;++i) ans=ans*n%p;
for(int i=;i<=n-;++i) ans=ans*i%p;
printf("%lld\n",ans);
}