Loj 6044 共

Posted on | Views:

求完全二分图的生成树个数.

确定 $1$ 为根,钦定 $k$ 个节点的深度为奇数的方案数为 $\binom{n-1}{k-1}$ ,接下来只需要考虑合法连边的方案数.

显然树边只会出现在深度为奇与深度为偶的节点之间,方案数等价于完全二分图 $K_{k,n-k}$ 的生成树个数.

可以用 prufer 序列计算,或者用矩阵树定理,写出基尔霍夫矩阵后 手动爆算行列式 .

可以得到结论, $K_{n,m}$ 的生成树个数为 $n^{m-1}\cdot m^{n-1}​$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
int P;
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	} 
	return res;
}
const int N = 5e5 + 10;
int fac[N], invfac[N];
int binom(int n, int m)
{
	return mul(fac[n], mul(invfac[m], invfac[n - m]));
}
int calc(int n, int m)
{
	return mul(fpow(n, m - 1), fpow(m, n - 1));
}
int n, k;
int main()
{
	n = read(), k = read(), P = read();
	fac[0] = 1;
	for (int i = 1; i <= n; ++i)
		fac[i] = mul(fac[i - 1], i);
	invfac[n] = fpow(fac[n], P - 2);
	for (int i = n - 1; i >= 0; --i)
		invfac[i] = mul(invfac[i + 1], i + 1);
	int ans = mul(binom(n - 1, k - 1), calc(k, n - k));
	printf("%d\n", ans);
	return 0;
}