Prufer 编码

https://en.wikipedia.org/wiki/Prüfer_sequence

Cayley 公式

https://en.wikipedia.org/wiki/Cayley's_formula

二分图版本

P4430 小猴打架

https://www.luogu.com.cn/problem/P4430

题目描述

一开始森林里面有N只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过N-1次打架之后，整个森林的小猴都会成为好朋友。
现在的问题是，总共有多少种不同的打架过程。
比如当N=3时，就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的打架过程。

输入格式

一个整数N。

输出格式

一行，方案数mod 9999991。

样例 #1

样例输入 #1

4

样例输出 #1

96

提示

50%的数据N<=10^3。
100%的数据N<=10^6。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, p = 9999991;
long long ans = 1;
int main() {
	cin >> n;
	for (int i = 0; i < n - 2; i++) {
		ans = ans * n % p;
	}
	for (int i = 1; i <= n - 1; i++) {
		ans = ans * i % p;
	}
	cout << ans << endl;
}

题解

P4981 父子

https://www.luogu.com.cn/problem/P4981

题目背景

上演在各大学男生寝室的日常 $:$

$A :$ “我没带纸，快来厕所救我！”

$B :$ “叫爸爸。”

$A :$ “爸爸！”

$............................................$

$A :$ “我没钱了，能借我点吗。”

$B :$ “叫爸爸。”

$A :$ “爸爸！”

一个月后、

$B :$ “能把钱还给我吗。”

$A :$ “叫爸爸。”

$B :$ “爸爸！”

题目描述

对于全国各大大学的男生寝室，总是有各种混乱的父子关系。

那么假设现在我们一个男生寝室有不同的 $n$ 个人，每个人都至多有一个“爸爸”，可以有多个“儿子”，且有且只有一个人没有“爸爸”(毕竟是室长，还是要给点面子，当然了，室长人人当嘛)。

那么现在问题来了，对于一个有 $n$ 个人的寝室，最多可能存在多少种父子关系，当然每个人之间都必须要有直接或间接的父子关系。

输入格式

第一行一个 正整数 $t$，表示有组数据。

接下来 $t$ 行，每行一个整数 $n$，表示有 $n$ 个人。

输出格式

共 $t$ 行，每行一个整数，求关系个数。

由于答案可能较大，则我们需要输出答案对 $10^9+9$ 取模的值。

样例 #1

样例输入 #1

1
3

样例输出 #1

9

样例 #2

样例输入 #2

1
323

样例输出 #2

283888610

提示

• 对于 $10\%$ 的数据，保证 $t=0$；

• 另有 $30\%$ 的数据，保证 $n≤5$；

• 对于 $100\%$ 的数据，$t≤10^4$，$n≤10^9$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int t, n, p = 1000000009;
long long pw(long long x, long long y, long long p) {
	long long re = 1;	
	for (; y; y >>= 1) {
		if (y & 1) {
			re = re * x % p;
		}
		x = x * x % p;
	}
	return re;
}
int main() {
	cin >> t;
	for (int tt = 0; tt < t; tt++) {
		cin >> n;
		cout << pw(n, n - 1, p) << endl;
	}
}

题解

P2290 [HNOI2004]树的计数

https://www.luogu.com.cn/problem/P2290

题目描述

一个有 $n$ 个节点的树，设它的节点分别为 $v_1,v_2,\ldots,v_n$，已知第 $i$ 个节点 $v_i$ 的度数为 $d_i$，问满足这样的条件的不同的树有多少棵。

输入格式

输入文件第一行是一个正整数 $n$ ，表示树有 $n$ 个结点。第二行有 $n$ 个数，第 $i$ 个数表示 $d_i$，即树的第 $i$ 个结点的度数。

输出格式

输出满足条件的树有多少棵。

样例 #1

样例输入 #1

4                     
2 1 2 1

样例输出 #1

2

提示

$1\le n\le 150$，保证满足条件的树不超过 $10^{17}$ 个。

参考代码

#include <bits/stdc++.h>
using namespace std;
unsigned long long z = 1;
int n, x, s;
int main()
{
	scanf("%d", &n);
	for (int i = 0, k = 0; i < n; i++)
	{
		scanf("%d", &x);
		if (n > 1 && x == 0)
		{
			z = 0;
		}
		s += x;
		for (int j = 1; j < x; j++)
		{
			z = z * ++k / j;
		}
	}
	if (s != n * 2 - 2)
	{
		z = 0;
	}
	printf("%llu\n", z);
	return 0;
}

题解

https://acm.hdu.edu.cn/showproblem.php?pid=5629
P2624 [HNOI2008]明明的烦恼