跳转至

K - 堆里的 NaN

基本信息

题目出处2022 ICPC 亚洲区域赛南京站
队伍通过率7/465 (1.5%)

总体思路

完全二叉树中，除了最后一个节点的祖先节点（称为特殊点）以外，其它节点的子树都是满二叉树。因此讨论 NaN 节点是否在特殊点即可。

详细题解

以下题解中，用“高度”表示一棵二叉树有多少层，而用“深度”表示某一个节点位于第几层。例如，对于一棵高度为 3 的满二叉树（也就是说，有 23−1 个节点的满二叉树），节点 1 的深度为 1，而节点 6 的深度为 3。

常用结论

首先，您需要知道一个常用结论。考虑以下问题。

给定一棵 n 个节点的树，在每个节点中填一个从 1 到 n（含两端）的数，要求每个节点填的数都不一样，且后代节点的数要比祖先节点的数大。求方案数。这个问题有个比较常见的名字，就是“树的拓扑序计数”

这个问题的答案是 n!∏u∈Tsu，其中 T 表示树的所有节点构成的集合，su 表示以 u 为根的子树中有几个节点。也就是说，答案就是 n 的阶乘除以每个子树大小的乘积。

常用结论的证明

递推方程

令 f(i) 表示以节点 i 为根的子树的拓扑序数量，si 表示子树 i 中的节点数量，则递推方程如下：

f(u)=(su−1)!×∏v∈son(u)f(v)sv!

递推方程的解释如下。

首先，拓扑序里的第一个位置一定是节点 u 占据的，子树里的节点只能占据剩下的 (su−1) 个位置。由于不同子树里的节点不会互相影响，因此我们先给每个子树分好位置，然后再乘上每个子树内部的方案数即可。

给每个子树分好位置的方案数，相当于共有 |son(u)| 种颜色的球，其中第 v 种颜色的球共有 sv 个，求排列的方案数。这是经典的可重排列问题，方案数为

(∑sv)!=(su−1)!∏sv!

然后再乘上每个子树内部的方案数，即 ∏f(v)，就得到了递推方程。

公式证明

对子树使用数学归纳法，把答案公式套进递推方程。

f(u)=(su−1)!×∏v∈son(u)sv!÷∏v∈son(u)∏w∈tree(v)sw÷∏v∈son(u)sv!=(su−1)!÷∏w∈tree(u)∖usw=su!÷∏w∈tree(u)sw

◼

套用结论

接下来回到原问题。根据堆的性质，我们可以把原问题转化为以下计数问题。

给定一棵 n 个节点的完全二叉树，选择一个节点 u，将完全二叉树分为以 u 为根的子树 U 和子树之外的部分 U′。将 0 填入节点 u 中，还需要将 1 到 (n−1) 填入 U 和 U′ 中，使得 U 和 U′ 分别满足后代节点的数要比祖先节点的数大。求方案数。

尝试套用上面的常用结论计算答案。设 (nm) 表示从 n 个物品里选 m 个的组合数，P 表示 U 中每个子树大小的乘积，P′ 表示 U′ 中每个子树大小的乘积，答案为

su!P×(n−su)!P′×(n−1su−1)=su!P×(n−su)!P′×(n−1)!(su−1)!×(n−su)!=(n−1)!×suP×P′

只要 0 的位置不一样，肯定就是不同的方案，因此最终总的方案数就是 ∑u=1n(n−1)!×suP×P′。因为我们算的是从 n! 个排列中等概率抽取的概率，因此概率就是总方案数除以 n!，即 ∑u=1nsuP×P′×n。

直接计算这个式子的复杂度至少是 O(n) 的，但完全二叉树中有许多同构的子树，可以帮助我们减少计算。

完全二叉树的性质

具体来说，完全二叉树具有如下性质：称完全二叉树中编号最大的点以及它的祖先节点为“特殊点”，除了特殊点以外，以其它任意一个点为根的子树都是满二叉树。如下图所示，红色的点就是特殊点，而以任意一个黑色点为根的子树都是满二叉树。

k-editorial.png

另外还可以发现，除了节点 1 以外，每一个特殊点都有一个根节点与它同深度的满二叉子树。称该满二叉树为该特殊点的“兄弟树”。例如，节点 2 的兄弟树是以节点 3 为根的满二叉树，节点 5 的兄弟树是以节点 4 为根的满二叉树。节点 20 虽然看似没有兄弟树，但可以认为节点 20 也有一棵高度为 0 的兄弟树。

因为兄弟树是满二叉树，所以我们只关心它的高度。设整棵树高度为 D，某个特殊点的深度为 d。如果该特殊点是父节点的左子节点，那么兄弟树的高度为 (D−d)；如果该特殊点是父节点的右子节点，那么兄弟树的高度为 (D−d+1)。

记 sh(d) 表示深度为 d 的特殊点的兄弟树的高度，记 sz(d) 表示以深度为 d 的特殊点为根的子树中有几个节点。容易得到递推式：

sz(D)=1sz(d)=sz(d+1)+2sh(d)

预处理

接下来尝试计算 P 和 P′ 的值。首先预处理如下值。

  • g(i) 表示一棵高度为 i 的满二叉树，所有子树大小的乘积。容易得到递推式：
g(1)=1g(i)=g(i−1)×g(i−1)×(2i−1)
  • h(i,j) 表示一棵高度为 i 满二叉树，再去掉任意一棵高度为 j 的子树（要求 j≤i。也就是说，现在这棵树有 (2i−2j) 个节点），所有子树大小的乘积。容易得到递推式：
h(i,i)=1h(i,j)=h(i−1,j)×g(i−1)×(2i−2j)

容易得到整棵二叉树子树大小的乘积为

X=(∏d=1Dsz(d))×(∏d=2Dg(d))

预处理的复杂度是 O(log2⁡n)。

讨论 NaN 节点的位置

接下来我们讨论两种情况：u 是特殊点，以及 u 不是特殊点。

特殊点

如果 u 是特殊点，设该特殊点深度为 d，则所有以深度小于 d 的特殊点为根的子树的大小都将减少 sz(d)，而其它子树的大小不受影响。也就是说

su=sz(d)P×P′=X÷(∏i=1d−1sz(i))×(∏i=1d−1(sz(i)−sz(d)))

特殊点只有 log⁡n 个，枚举所有特殊点即可。这一部分的复杂度是 O(log2⁡n)。

非特殊点

如果 u 不是特殊点，那么它一定位于某个特殊点的兄弟树中。设它位于深度为 d 的特殊点的兄弟树中，且 u 的子树高度为 w，则所有以深度小于 d 的特殊点为根的子树的大小都将减少 (2w−1)，当然该兄弟树内部的节点也会受到影响，而其它子树的大小不受影响。

为了处理这一情况，我们另外计算以下值。

f(d,w)=∏i=1d(sz(d)−2w+1)

递推式就是

f(1,w)=n−2w+1f(d,w)=f(d−1,w)×(sz(d)−2w+1)

那么

su=2w−1P×P′=X÷(∏i=1d−1sz(i))×f(d−1,w)÷g(sh(d))×h(sh(d),w)

其中 ∏i=1d−1sz(i)=f(d−1,0)，所以式子可以 O(1) 计算。我们枚举特殊点以及 w 即可。另外，满足 d 和 w 的点 u 共有 2sh(d)−w 种，所以这一情况求出来的式子要乘以该值。这一部分的复杂度也是 O(log2⁡n)。

得到答案

答案就是两种情况加起来，另外除法需要通过逆元计算。总体复杂度 O(log2⁡nlog⁡M)。

参考代码

 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
#define MAXP 30
#define MOD ((int) 1e9 + 7)
using namespace std;

int n;
long long ans;

int sz[MAXP + 10];
long long f[MAXP + 10][MAXP + 10];
long long g[MAXP + 10], h[MAXP + 10][MAXP + 10];

long long power(long long a, long long b) {
    long long y = 1;
    for (; b; b >>= 1) {
        if (b & 1) y = y * a % MOD;
        a = a * a % MOD;
    }
    return y;
}

long long inv(long long x) {
    return power(x, MOD - 2);
}

// 预处理 g 与 h
void prepare() {
    g[0] = g[1] = 1;
    for (int i = 2; i <= MAXP; i++) g[i] = g[i - 1] * g[i - 1] % MOD * ((1 << i) - 1) % MOD;
    h[1][1] = 1;
    for (int i = 2; i <= MAXP; i++) {
        for (int j = 1; j < i; j++) h[i][j] = h[i - 1][j] * g[i - 1] % MOD * ((1 << i) - (1 << j)) % MOD;
        h[i][i] = 1;
    }
}

void solve() {
    scanf("%d", &n);
    int D = 0;
    for (int x = n; x; x >>= 1) D++;

    memset(sz, 0, sizeof(sz));
    memset(f, 0, sizeof(f));

    // 计算 sz 与 f
    sz[D] = 1;
    long long X = 1;
    for (int d = D, now = n; d > 1; d--) {
        int nxt = now >> 1;
        int z = now & 1 ? D - d + 1 : D - d;
        sz[d - 1] = sz[d] + (1 << z);
        X = X * g[z] % MOD;
        now = nxt;
    }

    for (int j = 0; j < D; j++) f[1][j] = n - ((1 << j) - 1);
    for (int i = 2; i <= D; i++) for (int j = 0, k = 0; k < sz[i]; j++, k = k * 2 + 1) f[i][j] = f[i - 1][j] * (sz[i] - k) % MOD;
    X = inv(X * f[D][0] % MOD);

    ans = 0;
    for (int d = D, now = n; ; d--) {
        // NaN 位于深度为 d 的特殊点
        long long t = X;
        for (int i = 1; i < d; i++) t = t * sz[i] % MOD * inv(sz[i] - sz[d]) % MOD;
        t = t * sz[d] % MOD * inv(n) % MOD;
        ans = (ans + t) % MOD;

        if (d == 1) break;

        // NaN 位于深度为 d 的兄弟树
        int nxt = now >> 1;
        int z = now & 1 ? D - d + 1 : D - d;
        for (int j = 1; j <= z; j++) {
            long long t = X * f[d - 1][0] % MOD * inv(f[d - 1][j]) % MOD;
            t = t * g[z] % MOD * inv(h[z][j]) % MOD;
            t = t * inv(g[j]) % MOD * ((1 << j) - 1) % MOD * inv(n) % MOD;
            t = t * (1 << (z - j)) % MOD;
            ans = (ans + t) % MOD;
        }
        now = nxt;
    }

    printf("%lld\n", ans);
}

int main() {
    prepare();
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}