[洛谷 4430,bzoj 1430]小猴打架

说来这道水题在bzoj上竟然还是权限题…

题目链接

https://www.luogu.org/problem/P4430

https://lydsy.com/JudgeOnline/problem.php?id=1430

题解

首先，让我们了解一下Cayley定理。

Cayley定理：有 \(n\) 个节点的不同形态的无根树的数量为 \(n^{n-2}\) 个。

而对于每个树，本质不同的连接方式有 \((n-1)!\) 个。

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

#include <iostream>
#define MOD 9999991
using namespace std;
int main()
{
 long long n,ans=1;
 cin>>n;
 for(int i=1;i<=n-2;i++)
  ans=(ans*n)%MOD;
 for(int i=1;i<=n-1;i++)
  ans=(ans*i)%MOD;
 cout<<ans<<endl;
 return 0;
}