自动搬运

查看原文

来自洛谷，原作者为

	da32s1da **

搬运于2025-08-24 22:00:06，当前版本为作者最后更新于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;
}