Galgame

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

把题目的“更有趣”关系看成所有本质不同有序二叉树的全序，先按结点数分类，再递归计算同大小树中的字典序排名。

OJ: luogu

题目 ID: P7118

难度:提高+/省选-

标签:树递归组合计数Catalan排名

日期: 2026-06-20 08:59

题意

把一款 Galgame 看成一棵有序二叉树：

每个结点是一个场景
左儿子表示选 A 后到达的场景
右儿子表示选 B 后到达的场景
0 表示空场景

题目定义了两棵树谁更有趣：

先比较可达场景总数
场景总数相同就比较左子树
左子树也相同再比较右子树

要求输出当前这棵树前面有多少个本质不同、并且更不有趣的 Galgame，答案对 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#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int n;
int lc[25], rc[25];

struct Node {
    int left;
    int right;
};

vector<Node> trees[15];
map<tuple<int, int, int>, int> id_of[15];

void init_all_trees(int max_size) {
    trees[0].push_back({-1, -1});

    for (int sz = 1; sz <= max_size; sz++) {
        for (int left_size = 0; left_size <= sz - 1; left_size++) {
            int right_size = sz - 1 - left_size;
            for (int i = 0; i < (int) trees[left_size].size(); i++) {
                for (int j = 0; j < (int) trees[right_size].size(); j++) {
                    tuple<int, int, int> state = make_tuple(left_size, i, j);
                    if (id_of[sz].count(state)) {
                        continue;
                    }
                    id_of[sz][state] = (int) trees[sz].size();
                    trees[sz].push_back({i, j});
                }
            }
        }
    }
}

int calc_size_from_input(int u) {
    if (u == 0) {
        return 0;
    }
    return calc_size_from_input(lc[u]) + calc_size_from_input(rc[u]) + 1;
}

int build_id_from_input(int u) {
    if (u == 0) {
        return 0;
    }

    int left_size = calc_size_from_input(lc[u]);
    int right_size = calc_size_from_input(rc[u]);
    int left_id = build_id_from_input(lc[u]);
    int right_id = build_id_from_input(rc[u]);
    int total_size = left_size + right_size + 1;

    return id_of[total_size][make_tuple(left_size, left_id, right_id)];
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> lc[i] >> rc[i];
    }

    init_all_trees(n);

    int total_size = calc_size_from_input(1);
    int rank_in_same_size = build_id_from_input(1);

    i64 ans = 0;
    for (int i = 1; i < total_size; i++) {
        ans += (int) trees[i].size();
    }
    ans += rank_in_same_size;

    cout << ans << '\n';

    return 0;
}

这个暴力会把所有本质不同的小规模有序二叉树全部生成出来，再按题目规则给它们编号。

所以这题本质上就是求：

当前这棵有序二叉树
在所有本质不同有序二叉树组成的全序里
排名是多少

关键拆分

答案可以拆成两部分：

结点数更小的所有树数量
与当前树结点数相同，但更不有趣的树数量

第一部分很好办，因为有序二叉树的本质不同结构数正是 Catalan 数。

设：

cat[i] 表示 i 个结点的本质不同有序二叉树数量

那么第一部分就是：

cat[1] + cat[2] + ... + cat[sz[root]-1]

同大小内部排名

设当前结点 u：

左子树大小是 ls
右子树大小是 rs

定义：

rank[u]：u 这棵树在所有大小为 sz[u] 的树中的排名，从 0 开始

则同大小下所有更不有趣的树分成三段：

部分	数量
左子树大小更小	`sum cat[x] * cat[sz[u]-1-x]`
左子树大小相同，但左子树排名更小	`rank[left] * cat[rs]`
左子树完全相同，右子树排名更小	`rank[right]`

所以：

rank[u] = sum_{x=0}^{ls-1} cat[x] * cat[sz[u]-1-x] + rank[left] * cat[rs] + rank[right]

递推公式与排名公式

对每个结点 u，需要维护两个量：

sz[u] = sz[lc[u]] + sz[rc[u]] + 1

rank[u] = \sum_{x=0}^{ls-1} cat[x] \cdot cat[sz[u]-1-x] + rank[lc[u]] \cdot cat[rs] + rank[rc[u]]

最终答案是：

pre\_cat[sz[1]-1] + rank[1]

第一项如果直接枚举，在极端结构下会很慢。

这里继续利用 Catalan 总和：

cat[sz[u]] = sum_{x=0}^{sz[u]-1} cat[x] * cat[sz[u]-1-x]

如果左子树比较大，就改成“总数减补集”，于是每个结点只需要枚举左右子树里较小的一边。

最后答案就是：

pre_cat[sz[root]-1] + rank[root]

其中 pre_cat[i] 是 cat 的前缀和。

代码

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int MAXN = 1000000 + 5;
const i64 MOD = 998244353LL;

int n;
int lc[MAXN], rc[MAXN];
int sz[MAXN];          // sz[u] 表示以 u 为根能到达的场景总数
i64 cat[MAXN];         // cat[i] 表示 i 个结点的本质不同二叉树数量（Catalan 数）
i64 pre_cat[MAXN];     // pre_cat[i] = cat[1] + ... + cat[i]
i64 rank_in_size[MAXN];// rank_in_size[u] 表示在“结点数相同”的所有本质不同 Galgame 中的排名（从 0 开始）
i64 inv[MAXN];

inline int read_int() {
    int x = 0;
    int f = 1;
    int ch = getchar();

    while (ch != '-' && (ch < '0' || ch > '9')) {
        ch = getchar();
    }
    if (ch == '-') {
        f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main() {
    n = read_int();
    for (int i = 1; i <= n; i++) {
        lc[i] = read_int();
        rc[i] = read_int();
    }

    // 预处理 Catalan 数。
    inv[1] = 1;
    for (int i = 2; i <= n + 1; i++) {
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
    }

    cat[0] = 1;
    for (int i = 1; i <= n; i++) {
        cat[i] = cat[i - 1] * (4LL * i - 2) % MOD;
        cat[i] = cat[i] * inv[i + 1] % MOD;
        pre_cat[i] = (pre_cat[i - 1] + cat[i]) % MOD;
    }

    // 非递归后序遍历，避免深链爆栈。
    vector<int> order;
    order.reserve(n);
    vector<int> st;
    st.reserve(n);
    st.push_back(1);

    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        order.push_back(u);

        if (lc[u] != 0) {
            st.push_back(lc[u]);
        }
        if (rc[u] != 0) {
            st.push_back(rc[u]);
        }
    }

    for (int i = (int) order.size() - 1; i >= 0; i--) {
        int u = order[i];
        sz[u] = sz[lc[u]] + sz[rc[u]] + 1;
    }

    for (int i = (int) order.size() - 1; i >= 0; i--) {
        int u = order[i];
        int left_size = sz[lc[u]];
        int right_size = sz[rc[u]];
        int total_size = sz[u];

        i64 ans = 0;

        // 第一段：
        // 左子树大小更小的所有情况。
        // 利用 Catalan 总和，只枚举更小的一边。
        if (left_size <= right_size) {
            for (int x = 0; x < left_size; x++) {
                ans += cat[x] * cat[total_size - 1 - x] % MOD;
                if (ans >= MOD) {
                    ans -= MOD;
                }
            }
        }
        else {
            ans = cat[total_size];
            for (int y = 0; y <= right_size; y++) {
                ans -= cat[total_size - 1 - y] * cat[y] % MOD;
                if (ans < 0) {
                    ans += MOD;
                }
            }
        }

        // 第二段：左子树大小相同，但左子树本身更不有趣。
        ans += rank_in_size[lc[u]] * cat[right_size] % MOD;
        ans %= MOD;

        // 第三段：左子树完全相同，再比较右子树。
        ans += rank_in_size[rc[u]];
        ans %= MOD;

        rank_in_size[u] = ans;
    }

    // 有趣度 = 所有结点数更少的本质不同 Galgame 数量
    //        + 在同样结点数下更不有趣的数量。
    i64 ans = pre_cat[sz[1] - 1] + rank_in_size[1];
    ans %= MOD;

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

    return 0;
}

复杂度

预处理 Catalan 数 $O(n)$
两次 DFS $O(n)$
排名计算部分整体 $O(n log n)$
额外使用若干长度为 n 的数组
总空间复杂度 $O(n)$

总结

这题最关键的是把原题的“有趣度比较”翻译成一棵有序二叉树的全序排名问题。

一旦看出这一点，后面就只是在做：

Catalan 数计数
同大小树的递归字典序排名

一图流解析

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

P7118 Galgame

题目背景

众所周知，as_lky 喜欢 Galgame。

题目描述

as_lky 搞到了很多 Galgame（真的很多！）。一款 Galgame 可以被描述为很多场景（Scene）的结合，它们形成了一棵 以 1 为根 的二叉树，每一个结点都是一个场景，一个结点的左儿子和右儿子分别对应在该场景选 A 选项和 B 选项能够到达的场景（可能会到达空场景，即游戏结束），我们称其为 A 场景和 B 场景。

as_lky 如下定义了两个不同的 Galgame 场景哪个更有趣（两款 Galgame 谁更为有趣也就取决于它们的初始场景谁更有趣）：

如果这两个场景能够到达的场景总数（即通过任意选择能够到达的不同场景总数，包括该场景本身）不一样，那么能到达的场景数更多的那个更有趣；
如果这两个场景的 A 场景不一样有趣，那么 A 场景更有趣的场景更有趣；
否则这两个场景谁更有趣完全等价于他们 B 场景谁更有趣。

值得注意的是，空场景能到达的场景数被定义为 0。

例如，对于上图给出的例子（若无法正常查看请 右键 -> 查看图像），我们这样判定 1 和 7 这两个场景谁更有趣：

首先，1 和 7 能到达的场景数都是 6，因此我们首先尝试比较其 A 场景：2 和 8。
由于 2 和 8 能到达的场景数不同（分别是 3 和 2），则 2 场景比 8 场景更有趣；继而可以得到 1 场景比 7 场景更有趣。

as_lky 定义两个 Galgame 场景本质相同，当且仅当这两个场景都为空场景，或者它们的 A 场景本质相同且 B 场景本质相同。

as_lky 认为一款 Galgame 的有趣度是所有可能的、本质不同的、不及这款 Galgame 有趣的 Galgame 数量。现在 as_lky 给了你一款 Galgame，请告诉他这款 Galgame 的有趣度是多少。as_lky 觉得这个数字可能有些大，所以他想让你输出这个数字对 $998244353$ 取模的结果。

输入格式

第一行一个正整数 $n$ ，代表这款 Galgame 中共有多少场景。

接下来 $n$ 行，每行两个非负整数 $a_i$ 和 $b_i$ ，分别代表该场景的 A 场景和 B 场景，0 代表空场景。保证数据合法。

输出格式

一行一个非负整数，代表有趣度对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

输入输出样例 #3

输入 #3

text

输出 #3

text

说明/提示

样例解释

样例一：下图分别给出了 as_lky 给你的 Galgame（左）和所有四种没有该 Galgame 有趣的 Galgame（右）：（若无法正常查看请 右键 -> 查看图像）

测试点约束

本题采用捆绑测试。

对于全部数据，有 $1\le n\le 10^6$ ， $0\le a_i,b_i\le n$ 。

每个子任务的具体限制见下表：

子任务编号	分值	$n\le$	特殊性质
1	10	$10$	$\times$
2	20	$5000$	$\times$
3	30	$10^6$	$\surd$
4	40	$10^6$	$\times$

特殊性质：保证数据均匀随机生成，即 $n$ 给定时，若所有场景数为 $n$ 的本质不同 Galgame 共有 $S$ 种，则每种本质不同的 Galgame 出现概率均为 $\frac{1}{S}$ 。

本题读入量较大，请使用较快的读入方式。

Galgame

目录

题意

思路

关键拆分

同大小内部排名

递推公式与排名公式

代码

复杂度

总结

一图流解析