小猴打架

wjh15101051's space

卧薪尝胆，厚积薄发。

小猴打架

Date: Thu Nov 01 16:15:17 CST 2018

In Category: NoCategory

Description：

给出 $n$ 个点的完全图，每次选择任意一条边，问这样 $n−1$ 次后得到一棵树的方案数是多少。

$1\leqslant n\leqslant 10^6$

Solution：

把答案分成两部分，最后的结果就是生成一棵树的方案数 $\times$ 为这棵树分配标号的方案数，第一问的话，根据 $prufer$ 序列方案数是 $n^{n-2}$ ，第二问就是 $(n-1)!$ 。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MOD 9999991

int n;

int main()

{

	int ans = 1;

	scanf("%d",&n);

	for(int i = 1;i < n;++i)ans = 1ll * ans * i % MOD;

	for(int i = 1;i <= n - 2;++i)ans = 1ll * ans * n % MOD;

	cout << ans << endl;

	return 0;

}

In tag: 树-prufer序列

wjh15101051