洛谷P6862 [RC-03] 随机树生成器 题解

发表于 | 分类于

题意：
$n$ 个节点的树，第 $i$ 个节点选择 $[1, i)$ 中一个点作为它的父节点。
求可能生成的所有 $n$ 个节点的树第 $k$ 个节点的度数之和。
$T \leq 10^5$，$n,k \leq 10^7$

数据很大，根据数据范围可以猜测复杂度为 $O(T polylog(n) polylog(k))$

然而感觉这个 $polylog(n)$ 和 $polylog(k)$ 没意义啊

所以考虑推柿子，每次 $O(1)$ 算答案

先看它往上走的度数

显然就是它的父节点贡献的度数

如果 $k=1$，显然 $k$ 号节点就是根节点，没有往上的度数

否则易知无论什么样的树它都有父节点，而树的总数是 $(n-1)!$，所以往上的度数就是 $(n-1)!$

把 $x!$ 做个前缀和，这一部分就是 $O(1)$ 的了

再看往下的度数，也就是它的子节点给它贡献的度数

$m$ 节点选中 $k$ 的情况占总情况数的 $\dfrac{1}{m - 1}$，对于所有 $k < m \leq n$ 都成立

那么所有这样的 $m$ 贡献的度数加起来 就是 $(n-1)!(\dfrac{1}{k} + \dfrac{1}{k + 1} + … + \dfrac{1}{n - 1})$

把 $\dfrac{1}{x}$ 做个前缀和，这一部分就也是 $O(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
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define ll long long

using namespace std;

inline bool is_digit(char c) {
	return c >= '0' && c <= '9';
}

inline int read() {
	int tmp = 0, f = 1;
	char c = getchar();
	while(!is_digit(c)) {
		if(c == '-') f = -f;
		c = getchar();
	}
	while(is_digit(c)) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48), c = getchar();
	return tmp * f;
}

inline void write(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar((x % 10) ^ 48);
}

int n, p = 1000000009;
ll inv[10000010], f[10000010];

inline ll qpow(ll a, ll q) {
	ll w = 1LL;
	while(q) {
		if(q & 1) w *= a, w %= p;
		a *= a, a %= p;
		q >>= 1;
	}
	return w % p;
} 

int main() {
    inv[1] = 1;
    for(register int i = 2; i <= 10000000; i++) {
        inv[i] = - (p / i) * inv[p % i];
        inv[i] = (inv[i] % p + p) % p;
    }
    for(register int i = 1; i <= 10000000; i++) {
    	inv[i] += inv[i - 1];
    	inv[i] %= p;
    }
    f[0] = 1;
    for(register int i = 1; i <= 10000000; i++) {
    	f[i] = 1ll * f[i - 1] * i % p;
    }
    int t = read();
    while(t--) {
    	int n = read(), k = read();
    	long long ans = 0;
    	if(k != 1) ans += f[n - 1];
    	ans %= p;
    	ans += ((inv[n - 1] - inv[k - 1]) % p + p) % p * f[n - 1] % p;
    	ans %= p;
    	write(ans), putchar(10);
    }
    return 0;
}