Description
给你一个正整数 $n$ ，请你求出 $n$ 个互不相同的数能构成多少个不同的大小为 $n$ 的二叉堆，答案模 $(10 ^ 9 + 7)$ 。
Solution
考虑 递推 ，设 $f[i]$ 表示大小为 $i$ 的二叉堆的个数，那么设 $i$ 号点的左儿子为 $l$ 号点，右儿子为 $r$ 号点，并设 $size_i$ 表示以 $i$ 号点为根的子树的大小。那么有 $f[i] = (_{size_l} ^ {\;i - 1})f[size_l]f[size_r]$ 。
当只有一个儿子时， $f[i] = f[size_l]$ 。
对于组合数，我们可以先把阶乘预处理出来，当然也可以顺便预处理逆元，其实逆元暴力算也行。
到这里，我们得到了一个时间复杂度为 $O(n \log (10^9 +7))$ 的做法。
题解说会卡，然而我过了，而且跑得不慢。
此题还有 $O(n)$ 的做法，交由读者练习。
Code
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
66
67
68
69
70
71
72
73
74
75
76
| #include <cstdio>
#define mod 1000000007LL
#define maxN 5000010
long long size[maxN], fac[maxN], f[maxN];
long long n = 0;
long long pow (long long x, long long y)
{
if(!y)
{
return 1;
}
else
{
long long dq = pow(x, y / 2);
if(!(y % 2))
{
return dq * dq % mod;
}
else
{
return dq * dq % mod * x % mod;
}
}
}
long long inv (long long x)
{
return pow(x, mod - 2);
}
long long C (long long n, long long m)
{
return fac[n] * inv(fac[m]) % mod * inv(fac[n - m]) % mod;
}
void dfs (long long x)
{
size[x] = 1;
long long lson = x * 2, rson = x * 2 + 1;
if(lson <= n)
{
dfs(lson);
size[x] += size[lson];
if(rson <= n)
{
dfs(rson);
size[x] += size[rson];
if(!f[size[x]])
{
f[size[x]] = C(size[x] - 1, size[lson]) * f[size[lson]] % mod * f[size[rson]] % mod;
}
}
else
{
if(!f[size[x]])
{
f[size[x]] = f[size[lson]] % mod;
}
}
}
}
int main ()
{
scanf("%lld", &n);
fac[0] = 1;
for(long long i = 1;i <= n; i++)
{
fac[i] = fac[i - 1] * i % mod;
}
if(n == 1)
{
printf("1");
return 0;
}
f[1] = 1;
dfs(1);
printf("%lld", f[n] * 2 % mod);
return 0;
}
|