跳转至

K - 堆里的 NaN

基本信息

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

总体思路

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

详细题解

以下题解中,用“高度”表示一棵二叉树有多少层,而用“深度”表示某一个节点位于第几层。例如,对于一棵高度为 \(3\) 的满二叉树(也就是说,有 \(2^3 - 1\) 个节点的满二叉树),节点 \(1\) 的深度为 \(1\),而节点 \(6\) 的深度为 \(3\)

常用结论

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

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

这个问题的答案是 \(\frac{n!}{\prod\limits_{u \in \mathbb{T}} s_u}\),其中 \(\mathbb{T}\) 表示树的所有节点构成的集合,\(s_u\) 表示以 \(u\) 为根的子树中有几个节点。也就是说,答案就是 \(n\) 的阶乘除以每个子树大小的乘积。

常用结论的证明

递推方程

\(f(i)\) 表示以节点 \(i\) 为根的子树的拓扑序数量,\(s_i\) 表示子树 \(i\) 中的节点数量,则递推方程如下:

\[ f(u) = (s_u - 1)! \times \prod\limits_{v \in \text{son}(u)} \frac{f(v)}{s_v!} \]

递推方程的解释如下。

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

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

\[ \frac{(\sum s_v)! = (s_u - 1)!}{\prod s_v!} \]

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

公式证明

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

\[ \begin{matrix} f(u) & = & (s_u - 1)! \times \prod\limits_{v \in \text{son}(v)} s_v! \div \prod\limits_{v \in \text{son}(v)}\prod\limits_{w \in \text{tree}(v)} s_w \div \prod\limits_{v \in \text{son}(v)} s_v! \\ & = & (s_u - 1)! \div \prod\limits_{w \in \text{tree}(u) \backslash u} s_w \\ & = & s_u! \div \prod\limits_{w \in \text{tree}(u)} s_w \end{matrix} \]

\(\blacksquare\)

套用结论

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

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

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

\[ \begin{matrix} & \frac{s_u!}{P} \times \frac{(n - s_u)!}{P'} \times \binom{n - 1}{s_u - 1} \\ = & \frac{s_u!}{P} \times \frac{(n - s_u)!}{P'} \times \frac{(n - 1)!}{(s_u - 1)! \times (n - s_u)!} \\ = & \frac{(n - 1)! \times s_u}{P \times P'} \end{matrix} \]

只要 \(0\) 的位置不一样,肯定就是不同的方案,因此最终总的方案数就是 \(\sum\limits_{u=1}^n \frac{(n - 1)! \times s_u}{P \times P'}\)。因为我们算的是从 \(n!\) 个排列中等概率抽取的概率,因此概率就是总方案数除以 \(n!\),即 \(\sum\limits_{u=1}^n\frac{s_u}{P \times P' \times n}\)

直接计算这个式子的复杂度至少是 \(\mathcal{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\) 的特殊点为根的子树中有几个节点。容易得到递推式:

\[ \begin{matrix} sz(D) = 1 \\ sz(d) = sz(d + 1) + 2^{sh(d)} \end{matrix} \]

预处理

接下来尝试计算 \(P\)\(P'\) 的值。首先预处理如下值。

  • \(g(i)\) 表示一棵高度为 \(i\) 的满二叉树,所有子树大小的乘积。容易得到递推式:
\[ \begin{matrix} g(1) = 1 \\ g(i) = g(i - 1) \times g(i - 1) \times (2^i - 1) \end{matrix} \]
  • \(h(i, j)\) 表示一棵高度为 \(i\) 满二叉树,再去掉任意一棵高度为 \(j\) 的子树(要求 \(j \le i\)。也就是说,现在这棵树有 \((2^i - 2^j)\) 个节点),所有子树大小的乘积。容易得到递推式:
\[ \begin{matrix} h(i, i) = 1 \\ h(i, j) = h(i - 1, j) \times g(i - 1) \times (2^i - 2^j) \end{matrix} \]

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

\[ X = (\prod\limits_{d=1}^D sz(d)) \times (\prod\limits_{d=2}^D g(d)) \]

预处理的复杂度是 \(\mathcal{O}(\log^2 n)\)

讨论 NaN 节点的位置

接下来我们讨论两种情况:\(u\) 是特殊点,以及 \(u\) 不是特殊点。

特殊点

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

\[ \begin{matrix} s_u = sz(d) \\ P \times P' = X \div (\prod\limits_{i=1}^{d-1}sz(i)) \times (\prod\limits_{i=1}^{d-1}(sz(i) - sz(d))) \end{matrix} \]

特殊点只有 \(\log n\) 个,枚举所有特殊点即可。这一部分的复杂度是 \(\mathcal{O}(\log^2 n)\)

非特殊点

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

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

\[ f(d, w) = \prod\limits_{i=1}^d (sz(d) - 2^w + 1) \]

递推式就是

\[ \begin{matrix} f(1, w) = n - 2^w + 1 \\ f(d, w) = f(d - 1, w) \times (sz(d) - 2^w + 1) \end{matrix} \]

那么

\[ \begin{matrix} s_u = 2^w - 1 \\ P \times P' = X \div (\prod\limits_{i=1}^{d-1}sz(i)) \times f(d - 1, w) \div g(sh(d)) \times h(sh(d), w) \end{matrix} \]

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

得到答案

答案就是两种情况加起来,另外除法需要通过逆元计算。总体复杂度 \(\mathcal{O}(\log^2 n \log 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;
}