『JROI-5』Color

GitHub 跳转原题关系图返回列表

把完全二叉树的不完整部分压缩成“最后一个叶子到根”的一条路径，预处理满树方案数后沿这条路径自底向上递推。

OJ: luogu

题目 ID: P8089

难度:提高+/省选-

标签:树形DP动态规划完全二叉树递推

日期: 2026-06-21 04:50

题意

给一棵 dep 层的完全二叉树。

要求统计有多少个“包含根节点的连通块”，答案对 998244353 取模。

思路

先看一个适合小数据验证的暴力：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;

vector<vector<int> > g;

long long dfs(int u, int fa) {
    long long ret = 1; // 只选当前根
    for (size_t i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa) {
            continue;
        }
        ret = ret * (dfs(v, u) + 1) % MOD;
    }
    return ret;
}

long long parse_binary(const string &s) {
    long long x = 0;
    for (size_t i = 0; i < s.size(); i++) {
        x = x * 2 + (s[i] - '0');
    }
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：显式建出小规模完全二叉树，再在真实树上递归统计。
    int T;
    cin >> T;
    while (T--) {
        int dep;
        string s;
        cin >> dep >> s;
        long long last_cnt = parse_binary(s);

        if (dep == 1) {
            cout << 1 << '\n';
            continue;
        }

        vector<long long> exist_pos;
        long long last_begin = 1LL << (dep - 1);
        long long last_end = last_begin + last_cnt - 1;

        long long total_pos = (1LL << dep) - 1;
        vector<int> id(total_pos + 2, 0);
        int tot = 0;

        for (int level = 1; level <= dep - 1; level++) {
            long long l = 1LL << (level - 1);
            long long r = (1LL << level) - 1;
            for (long long pos = l; pos <= r; pos++) {
                id[pos] = ++tot;
            }
        }
        for (long long pos = last_begin; pos <= last_end; pos++) {
            id[pos] = ++tot;
        }

        g.assign(tot + 1, vector<int>());
        for (long long pos = 1; pos <= total_pos; pos++) {
            if (id[pos] == 0) {
                continue;
            }
            long long lc = pos << 1;
            long long rc = lc | 1;
            if (lc <= total_pos && id[lc] != 0) {
                g[id[pos]].push_back(id[lc]);
                g[id[lc]].push_back(id[pos]);
            }
            if (rc <= total_pos && id[rc] != 0) {
                g[id[pos]].push_back(id[rc]);
                g[id[rc]].push_back(id[pos]);
            }
        }

        cout << dfs(1, 0) % MOD << '\n';
    }
    return 0;
}

如果树真的建出来，那么设 f(u) 表示“在 u 子树中，选出的连通块必须包含 u 的方案数”，就有：

f(u) = (f(ls)+1)(f(rs)+1)

因为左右子树都可以：

一个点不选
或者选一个包含对应儿子根节点的连通块

难点不在转移，而在树太大，不能显式建出来。

这题的关键观察是：

完全二叉树除了最后一层外，其余层都是满的
所以整棵树只有“最后一个叶子到根”的那条路径附近是不规则的
路径旁边挂着的子树，不是满树就是空树

于是先预处理：

A[h] = 高度为 h 的满二叉树方案数 + 1

满足：

A[0] = 1
A[h] = A[h-1]^2 + 1

递推公式

设 A[h] 表示高度为 h 的满二叉树“选一个包含根的连通块，或者整棵不选”的方案数，则：

A[0]=1,\quad A[h]=A[h-1]^2+1

沿最后一个叶子的路径自底向上回推时，若另一侧是高度为 t 的满子树，就有：

val \leftarrow A[t]\cdot (val+1)

然后把“最后一层节点个数”减一，得到最后一个叶子在底层的 0-based 编号。它的二进制表示，正好告诉我们从根到这个叶子的路径每一层是往左走还是往右走。

下面这张图展示了这种结构：

flowchart TD
  R["当前根"] --> L["继续递推的那一侧"]
  R --> F["另一侧是一棵满子树"]

所以可以自底向上回推：

一边继续带着当前 val
另一边直接乘预处理好的满树方案数

整题就从“指数级建树”变成了“扫一遍二进制路径”。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXD = 1000005;

int T;
int dep_arr[15];
string s_arr[15];
int max_dep;
long long A[MAXD];

string minus_one_binary(string s) {
    int n = (int) s.size();
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '1') {
            s[i] = '0';
            for (int j = i + 1; j < n; j++) {
                s[j] = '1';
            }
            return s;
        }
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    max_dep = 0;
    for (int i = 1; i <= T; i++) {
        cin >> dep_arr[i];
        cin >> s_arr[i];
        if (dep_arr[i] > max_dep) {
            max_dep = dep_arr[i];
        }
    }

    // A[i] = 满 i 层完全二叉树的方案数 + 1。
    // A[0] = 1 对应空树。
    A[0] = 1;
    for (int i = 1; i <= max_dep; i++) {
        A[i] = (A[i - 1] * A[i - 1] + 1) % MOD;
    }

    for (int tc = 1; tc <= T; tc++) {
        int dep = dep_arr[tc];
        string s = s_arr[tc];

        if ((int) s.size() < dep) {
            s = string(dep - (int) s.size(), '0') + s;
        }

        if (dep == 1) {
            cout << 1 << '\n';
            continue;
        }

        // c 表示最后一层节点数，r = c - 1。
        // 对 dep 位二进制做减一后，最高位一定是 0，后面的 dep-1 位
        // 正好描述“最后一个叶子”在底层从左到右的 0-based 位置。
        s = minus_one_binary(s);

        long long val = 1; // 高度为 1 的单点树，只有选根这一种方案。
        int cur_h = 1;

        // 从低位往高位回推，相当于不断把当前子树向上接一层父亲。
        for (int i = dep - 1; i >= 1; i--) {
            if (s[i] == '0') {
                val = A[cur_h - 1] * (val + 1) % MOD;
            } else {
                val = A[cur_h] * (val + 1) % MOD;
            }
            cur_h++;
        }

        cout << val % MOD << '\n';
    }

    return 0;
}

复杂度

预处理 $O(max dep)$ ，每组询问 $O(dep)$ ，总空间复杂度 $O(max dep)$ 。

总结

这题最值得记住的点是：

完全二叉树的不完整部分，可以压缩成一条路径
路径旁边的大块结构，都能用“满树递推值”一次处理掉

这是处理超大规模完全二叉树计数题时很常见的一类技巧。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P8089 『JROI-5』Color

题目背景

【被三月删除的图片】

泷泽三月 Orz

被删除图片会偷偷展示给报名讲评的同学（

题目描述

请注意到并不正常的时间限制。

小 C 有一棵 $dep$ 层 $n$ 个节点的完全二叉树，她希望选择其中一个包含根节点的连通块染色，她想知道有几种不同的染色方案，答案对 $998,244,353$ 取模。

输入格式

多测，第一行一个整数 $T$ ，表示测试组数。

对于每组数据

第一行一个整数 $dep$ ，同题意。

第二行一个整数 $s$ ，表示最底层叶子结点数目，特别的，他们将用二进制表示，你将读入一个 $dep$ 位 $\texttt{01}$ 串，用以表示 $s$ ，若转换为二进制后不足 $dep$ 位则用前缀 $0$ 补充。

保证数据合法。

输出格式

对于每组数据，一行一个整数，表示合法的染色方案的个数，需要换行。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

输入输出样例 #3

输入 #3

text

输出 #3

text

输入输出样例 #4

输入 #4

text

1见附件

输出 #4

text

1见附件

说明/提示

你可以通过学习 OI-Wiki 树基础来了解题面中的名词。

【样例解释】

对于样例 #1，可以画出如下所示二叉树。

我们对该二叉树按照前序遍历标号（如图），得到点集 $\left(1,2,3\right)$ 。

则仅有 $\left(1,2,3\right),\left(1,2\right),\left(1,3\right),\left(1\right)$ 是合法的染色方案。

对于样例 #3，可以画出如下所示二叉树。

我们对该二叉树按照前序遍历标号（如图），得到点集 $\left(1,2,3,4,5\right)$ 。

则仅有 $\left(1,2,3,4,5\right),\left(1,2,3,4\right),\left(1,2,3\right),\left(1,2,4\right),\left(1,2\right),\left(1,2,3,5\right),\left(1,2,4,5\right),\left(1,2,5\right),\left(1,5\right),\left(1\right)$ 是合法的染色方案。

显然 $\left(2,3,4\right),\left(1,3,4\right)$ 不是合法的染色方案，前者没有包含根节点，后者染色的点集不是联通的。

对于 $30\%$ 的数据， $1\leq T\leq 10, 1\leq dep \leq 20$ 。

对于另外 $20\%$ 的数据，树是满二叉树（即完美二叉树，perfect binary tree）。

对于 $100\%$ 的数据， $1\leq T\leq 10, 1\leq dep \leq 10^6$ 。

『JROI-5』Color

目录

题意

思路

递推公式

代码

复杂度

总结

一图流解析