题解 P4430 【小猴打架】

da32s1da · 2018-04-15 08:13:27 · 题解

题目大意：n个点，求构成生成树不同连接方式的方案数

首先需要知道prufer编码相关知识。

由 Cayley定理，n个节点的带标号的形态不同的无根树有n^{n-2}个，然后对于每棵树，生成方式有(n-1)!种，答案=(n-1)!*n^{n-2} mod 9999991

#include<cstdio>
#define mod 9999991
int n;long long ans=1;
int main()
{
    scanf("%d",&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;
    printf("%lld\n",ans);
    return 0;
}