形式化题目

给定一棵有根树：节点的孩子之间有顺序，每个节点涂一种颜色。机器人从根深度优先遍历，每进入一个房间（首次进入或从子节点返回都算）记录它的颜色，退出时不再记录，得到颜色序列 $S$。问：有多少种不同的（有序、带色的）树结构，其遍历序列恰好等于 $S$？答案对 $10^9$ 取模。

设树有 $n$ 个节点：进入根 1 次、每条边向下走 1 次，共 $n + (n-1) = 2n-1$ 次记录，所以 $|S| = 2n-1$ 必为奇数，$n = (|S|+1)/2$。等价地，每个节点 $u$ 在序列中出现 $1 + \deg^+(u)$ 次（$\deg^+$ 为孩子数）：进入记 1 次，每从一个孩子返回再记 1 次。

样例 $S=$ ABABABA（$n=4$）输出 $5$。把树写成括号形式 根(孩子1, 孩子2, …)（孩子从左到右、括号内是颜色），产生该序列的 5 棵树为：

每棵树的遍历序列都恰好是 ABABABA，例如方案 4 A(B(A, A))：进入 A、进入 B、进入第一个孩子 A、返回 B、进入第二个孩子 A、返回 B、返回 A，记下 A B A B A B A。数出 5 棵就是样例答案；本文要算的正是"不枚举树也能得到这个 5"。

暴力解法

思路

按题意直接来：先由 $|S|=2n-1$ 定出房间数 $n=(|S|+1)/2$，然后枚举所有可能的金字塔再逐个验证：

1. 枚举全部 $n$ 节点的有序（平面）有根树——数量是 Catalan 数 $C_{n-1}$；
2. 枚举全部 $2^n$ 种节点着色；
3. 对每棵（树，着色）模拟机器人遍历，逐位比对序列，吻合则计数加一。

思路天然正确，它也正是本文的对拍基准：验证阶段用它对 $n \leqslant 5$ 的全部有序树 × A/B 全着色做了全枚举，生成的 198 个不同序列与正解逐一比对、0 处不一致（记录见过程文档 04-correctness-and-edge-cases.md）。但规模双重爆炸：Catalan 数与指数同时相乘，$n=150$ 时约 $10^{131}$。

代码

本层不单独给出 brute.cpp：任务约定本题不写 brute/不对拍，暴力与正解没有可共用的输入输出结构，单独放一份只做"枚举+模拟"的文件不会带来新信息；上面的枚举步骤加样例表已经完整描述了这一层的全部行为；比对结果见上文思路末尾与过程文档 04-correctness-and-edge-cases.md。

复杂度

枚举总数 $C_{n-1}\cdot 2^{n}$，每次还要 $O(n)$ 模拟：

$n=5$ 时才一千多种，$n=10$ 已经五百万，到 $n=150$（$|S|=299$）是彻底的天文数字——"整棵枚举、整段验证"这条路在任何语言里都走不通。

瓶颈

瓶颈不只是"枚举太多"，更在于验证零复用：每次都"造整棵树 → 从头模拟整段序列"，相邻两次试错哪怕前半段完全相同也要整段重来。

要消除它，就要在序列上找到可以切开、彼此独立的边界，让"前半段怎么合法"和"后半段怎么合法"分别计数、再乘起来——这正是正解的出发点。

正解

思路

第一步：把序列按节点切成连续块。

固定节点 $u$（颜色 $c$）：机器人首次进入 $u$ 时记第一次，之后每从一个孩子返回 $u$ 又记一次，直到最后一次返回为止——这些记录在序列中是连续的一段，中间只插入以 $u$ 为根的子遍历。于是每个节点对应一个"块"，满足文法：

1
2块(c) := c (子块, c) (子块, c) ... (子块, c)
         ↑进入     ↑每个孩子遍历完返回 u 都记一次，直到走完全部孩子

三条直接推论：叶子的块是单元素 [c]；块首尾颜色都是 $c$；块长度 $= 1 + 2\times$（孩子数）恒为奇数。整个序列就是根的块，所以 $S[0]=S[m-1]$。

第二步：块的每一段都是连续区间。

子块是序列上的连续区间——子问题只由两个端点决定，这就是区间 DP 需要的封闭性。定义

第三步：按"第一个孩子"劈开，得到转移。

设 $s[l..r]$ 是块，$c=s[l]$。剥掉开头的根记录后，第一个子块占 $[l+1, k-1]$，位置 $k$ 是"从第一个孩子返回根"的记录（必须 $s[k]=c$）；剩下的 $[k, r]$ 恰好又是 $c\,(\text{子块},c)^*$ 形态——与块文法完全同型（文法只关心颜色与结构，位置 $k$ 上那条记录语义上是"进入"还是"返回"无关紧要），所以两半复用同一个 $f$ 计数、彼此独立：

$k \geqslant l+2$ 是因为首子块 $[l+1,k-1]$ 必须非空；条件 $s[k]=s[l]$ 只是必要过滤——孩子颜色可以与根相同，切分是否合法不能靠"找下一个同色位置"判断，而要交给两半的 DP 值自己说话，这也正是不能贪心匹配的原因。

正确性（不重不漏）：对区间长度归纳。任取产生 $s[l..r]$ 的子树，其第一个孩子的块有确定终点 $k$，两半分别由归纳对应求和中的某一项（不漏）；不同 $k$ 的第一孩子块终点不同，固定 $k$ 后两半解析由归纳各自唯一，乘积中每对解析拼出的树也不同（不重）。于是求和恰好每棵合法子树计一次，$f[0][m-1]$ 即为答案。

递推顺序：$f[l+1][k-1]$ 长度 $k-l-1$、$f[k][r]$ 长度 $r-k+1$ 都严格小于 $r-l+1$，按区间长度从小到大递推即可；合法块长度恒为奇数，只枚举奇数长度，偶数长度区间恒为 0。

样例 $S=$ ABABABA 的完整 DP 表（行 = 起点 $l$，列 = 终点 $r$，单元格 = $f[l][r]$，— 为 $l>r$ 空区间；由题目专用脚本 problem-analysis-workspace/viz_render.py 教学版复算）：

要观察三点：对角线全是 1（单房间自成一块）；非零格全落在首尾同色的奇数长度区间上（$f[0][3]$、$f[0][5]$ 都是 0）；答案直接读右上角 $f[0][6]=5$。最外层 $f[0][6]$ 的切分明细进一步展示乘法结构：

• $k=2$（A）：首子块 $f[1][1]=1$ × 余下 $f[2][6]=2$ → 贡献 2
• $k=4$（A）：首子块 $f[1][3]=1$ × 余下 $f[4][6]=1$ → 贡献 1
• $k=6$（A）：首子块 $f[1][5]=2$ × 余下 $f[6][6]=1$ → 贡献 2
• 合计 $2+1+2=5$，与样例输出一致。

代码

dp[i][j] 即 $f[i][j]$，初始化把 $f(i,i)=1$ 一次写好；外层按奇数 span 递推；if text[i] != text[j]: continue 实现首尾同色过滤；内层 for k in range(i + 2, j + 1) 枚举切分点，text[k] == root 过滤，left[k - 1] * dp[k][j] 就是 $f[i+1][k-1]\cdot f[k][j]$（left = dp[i + 1] 只是行引用别名，省掉内层一层索引）；每格写回前 % MOD（题面模数 $10^9$）。

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 金字塔：区间 DP，s[i..j] 单独作为一棵子树的方案数。
#include <cstdio>
#include <cstring>

typedef long long ll;

const ll MOD = 1000000000LL;
const ll MAXN = 305;

char text[MAXN];
ll dp[MAXN][MAXN];

int main() {
    if (scanf("%s", text) != 1) {
        printf("0\n");
        return 0;
    }
    ll n = (ll)strlen(text);

    // dp[i][j]：s[i..j] 单独作为一棵子树（连同它的遍历序列）的方案数
    for (ll i = 0; i < n; i++) dp[i][i] = 1; // 单个房间，进出各记一次

    for (ll span = 3; span <= n; span += 2) {
        for (ll i = 0; i + span - 1 < n; i++) {
            ll j = i + span - 1;
            if (text[i] != text[j]) continue; // 进入与退出记录的颜色必须都是根色
            char root = text[i];
            ll total = 0;
            // 切分点 k：第一棵子树占 s[i+1..k-1]，剩下的 s[k..j] 是同一层的其它子树
            for (ll k = i + 2; k <= j; k++) {
                if (text[k] == root) {
                    total = (total + (dp[i + 1][k - 1] % MOD) * (dp[k][j] % MOD)) % MOD;
                }
            }
            dp[i][j] = total % MOD;
        }
    }

    printf("%lld\n", n ? dp[0][n - 1] : 0);
    return 0;
}

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 20:55
# update_at: 2026-10-01 20:55

import sys

MOD = 10**9


def solve() -> None:
    text = sys.stdin.buffer.read().strip().decode()
    n = len(text)

    # dp[i][j]：s[i..j] 单独作为一棵子树（连同它的遍历序列）的方案数。
    # 长度偶数时不可能自成一棵子树（进入/退出成对），初值全为 0。
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1  # 单个房间，进出各记一次

    for span in range(3, n + 1, 2):
        for i in range(n - span + 1):
            j = i + span - 1
            if text[i] != text[j]:
                continue  # 进入与退出记录的颜色必须都是根色
            root = text[i]
            left = dp[i + 1]  # 剥掉根之后的内部序列，行下标固定，先取出来省一层索引
            total = 0
            # 切分点 k：第一棵子树占 s[i+1..k-1]，它自身的根色也是 root；
            # 剩下 s[k..j] 是同一层的其它子树（可以有多棵），由 dp[k][j] 收口。
            for k in range(i + 2, j + 1):
                if text[k] == root:
                    total += left[k - 1] * dp[k][j]
            dp[i][j] = total % MOD

    print(dp[0][n - 1] if n else 0)


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：状态数为奇数长度区间约 $m^2/4$ 个，每状态枚举 $O(m)$ 个切分点，合计 $O(m^3)$；$m=300$ 时最内层乘加约 $2\times10^{6}$ 次（大量 $k$ 被同色过滤跳过），实测最慢用例 0.143 s（时限 1000 ms）。
• 空间复杂度：$O(m^2)$ 的 dp 表，$300\times300$ 个整数，实测峰值 16.0 MB（限制 128 MB）。
• 验证记录：真实数据 25 组全部通过（verify.sh 3147：PASS=25 / FAIL=0，最慢 0.143 s）；另有上文暴力全枚举的 198 序列比对与样例 $5$ 复算，均一致。

总结

本题从"枚举树"到"区间 DP"的关键是一条结构性观察：遍历记录会按节点聚成连续的块，块满足文法 $c\,(\text{子块},c)^*$，于是

1. 块首尾同色、长度为奇数——先筛掉大批不可能的区间；
2. 子块是连续区间——子问题只由端点 $(l,r)$ 决定，$O(m^2)$ 个状态足够；
3. 块内按第一个孩子劈开——首子块 $[l+1,k-1]$ 与剩余 $[k,r]$ 同型、独立，乘法合并、对 $k$ 求和，得到 $O(m^3)$ 的区间 DP。

最危险的坑是颜色碰撞：孩子可以和根同色，返回根的记录与子块内记录无法靠颜色区分，所以切分点必须全部枚举、交给 DP 判定，而不是贪心找"下一个同色位"。答案对 $10^9$ 取模（不是 $10^9+7$），按区间长度递推保证依赖的更短区间先算好。

图示解析

从建模到答案的主线

这张图串起本题从读入序列到得到答案的推理链：

1
2
3
4
5
6
7
8
9
10
11输入颜色序列 S（机器人 DFS 序，长度 m = 2n - 1）
   |
   v
关键观察：每个节点的记录聚成连续块，文法  c (子块, c)*
   |        首尾同色、长度为奇数；整段序列 = 根的块
   v
区间 DP：f[l][r] = s[l..r] 恰为一个完整块的方案数
   |        按第一个孩子劈开：f[l][r] = sum f[l+1][k-1] * f[k][r]
   |        同色过滤 s[k]=s[l]，依赖区间更短 -> 按奇数长度递推
   v
答案 f[0][m-1]（mod 10^9）        O(m^3) 时间、O(m^2) 空间

顺着箭头看：每个节点都是"一条记录 + 若干（子块, 记录）对"，这决定了状态只需两个端点；切分点 $k$ 把区间劈成互相独立的两半，乘法合并消灭了暴力的重复验证；最后按长度递推把指数级枚举压成三次方。