陨石的秘密

形式化题目

一个字符串是 SS 表达式，当且仅当它能由下面 6 条规则生成：

空串是 SS 表达式；
若 $A$ 是 SS 表达式且 $A$ 中不含 { } [ ]，则 (A) 是 SS 表达式；
若 $A$ 是 SS 表达式且 $A$ 中不含 { }，则 [A] 是 SS 表达式；
若 $A$ 是 SS 表达式，则 {A} 是 SS 表达式；
若 $A,B$ 都是 SS 表达式，则 $AB$ 也是 SS 表达式。

规则 2–4 里的「不含某类字符」限定了每对括号的内部能装什么：() 内只允许 ()，[] 内允许 [] 和 ()，{} 内三种都允许。

SS 表达式的深度 $D(E)$ 定义为

D(E)=\begin{cases} 0, & E \text{ 是空串},\\ D(A)+1, & E=(A),\ [A] \text{ 或 } \{A\},\\ \max\bigl(D(A),D(B)\bigr), & E=AB. \end{cases}

给定 $L_1,L_2,L_3,D$ ，求深度恰好为 $D$ ，且恰好含 $L_1$ 对 {}、 $L_2$ 对 []、 $L_3$ 对 () 的 SS 表达式个数，对 $11380$ 取余。

正解

思路

卡点一：不能用「恰好」，要用「不超过」

先试着设 $\mathrm{exact}[i][j][k][d]$ 为「深度恰好为 $d$ 」的方案数，马上会卡在规则 5 上：拼接 $AB$ 的深度是 $\max(D(A),D(B))$ 。要判断它是否恰好为 $d$ ，就得知道左右两侧分别「恰好」还是「不超过」，分支会指数级展开。

把状态换成「深度不超过 $d$ 」， $\max$ 立刻变成两个不等式：

\max\bigl(D(A),D(B)\bigr)\leqslant d \iff D(A)\leqslant d \ \wedge\ D(B)\leqslant d.

于是乘法原理直接可用。题目要的是「恰好 $D$ 」，用两档上界相减还原即可：

\text{ans}=f[D][L_1][L_2][L_3]-f[D-1][L_1][L_2][L_3].

卡点二：任选切分会重复计数

如果只是「随便把串切成两段再相乘」，ABC 会被拆成 AB|C 和 A|BC 数两次。

解决办法是固定切法：规定每个非空 SS 串都按「首原子 + 剩余串」来拆，其中首原子指的是「第一个字符到与它匹配的那个右括号」这一段。这个位置由第一个字符唯一确定，所以拆分方式唯一，既不重也不漏。

例如 (){()}[] 的首原子是 ()，剩余是 {()}[]；继续拆剩余，得到下面这棵树。

text

1
2
3
4
5
6
7整个串 = (){()}[]   首原子 ()（() 层），剩余 {()}[]
  └─原子内 A = 空串  (深度 0)
  └─剩余 = {()}[]   首原子 {()}（{} 层），剩余 []
    └─原子内 A = ()   首原子 ()（() 层），剩余 空
      └─原子内 A = 空串  (深度 0)
    └─剩余 = []   首原子 []（[] 层），剩余 空
      └─原子内 A = 空串  (深度 0)

观察重点：每个非空 SS 串都被唯一地分解成一串原子，树上的每一次「└─剩余」都在消耗一个首原子。这也说明每层嵌套至少要吃掉一对括号，所以深度不可能超过括号总对数 $L_1+L_2+L_3$ 。

状态与转移

设 $f[d][i][j][k]$ 表示用了 $i$ 对 {}、 $j$ 对 []、 $k$ 对 () 且深度不超过 $d$ 的 SS 串个数。边界是

f[d][0][0][0]=1 \quad (\text{空串深度为 } 0,\text{ 对任何上界都合法}).

对非空格子，按首原子的三种括号类型分类。设原子内部用掉 $(a,b,c)$ 对括号，则剩余串用掉 $(i',j',k')$ ，首原子内层的深度必须 $\leqslant d-1$ （包裹加了一层），剩余串仍 $\leqslant d$ （拼接不抬高深度），并且规则 2–4 的内容限制会强制若干维为 $0$ ：

f[d][i][j][k]=\underbrace{\sum_{a<k} f[d][i][j][k-1-a]\cdot f[d-1][0][0][a]}_{(A)B} +\underbrace{\sum_{a<j}\sum_{b\leqslant k} f[d][i][j-1-a][k-b]\cdot f[d-1][0][a][b]}_{[A]B} +\underbrace{\sum_{a<i}\sum_{b\leqslant j}\sum_{c\leqslant k} f[d][i-1-a][j-b][k-c]\cdot f[d-1][a][b][c]}_{\{A\}B}

三个求和的含义是：先扣掉首原子自己占用的那一对括号，再把剩下的括号数分配给首原子内部与剩余串。 (A)B 里内层只能含 ()（ $i=j=0$ ）、[A]B 里内层不含 {}（ $i=0$ ）、{A}B 里内层无限制—— 这正是规则 2–4 的直接翻译。

枚举顺序：同层引用的 $f[d][i'][j'][k']$ 括号总数严格更少，所以按 $i,j,k$ 递增枚举就能保证被引用项已算好。外层 $d$ 从小到大递推， $f[d-1]$ 整层都是已知的。

下面的小表展示 $f[d][1][1][1]$ 随上界 $d$ 的变化，以及差分如何还原「恰好」。

$d$	$f[d][1][1][1]$ （不超过 $d$ ）	$f[d]-f[d-1]$ （恰好 $d$ ）
0	0	0
1	6	6
2	14	8
3	15	1

表格第一列是深度上界，第二列是不超过该上界的方案数，第三列是与上一档的差、也就是恰好为该深度的方案数。读法是： $L_1=L_2=L_3=1$ 时深度恰好为 $2$ 的串有 $8$ 个，正好等于样例输出；深度恰好为 $1$ 的有 $6$ 个（三个原子任意排列）；恰好为 $3$ 的只有 1 个（{[()]}，唯一的最深嵌套）。

答案与边界

答案取 $f[D]-f[D-1]$ ；当 $D=0$ 时只有空串一种（且要求 $L_1=L_2=L_3=0$ ），没有前一档，直接取 $f[0]$ 。另外若 $D>L_1+L_2+L_3$ ，由「每层嵌套至少吃一对括号」可知答案为 $0$ ，可以提前返回省掉建表。

代码

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/**
 * 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 13:00
 * update_at: 2026-10-10 13:00
 */

// 括号序列计数：四维 DP，深度不超过 d 的 SS 串数
#include <cstdio>
using namespace std;

typedef long long ll;

const int MOD = 11380; // 题面里的“当前年份”
const int MAXL = 12;   // 每种括号的对数上界
const int MAXD = 32;   // 深度上界

// le[d][i][j][k]：深度不超过 d、含 i 对 {}、j 对 []、k 对 () 的 SS 串数
ll le[MAXD][MAXL][MAXL][MAXL];

int main() {
    int L1, L2, L3, D;
    if (scanf("%d %d %d %d", &L1, &L2, &L3, &D) != 4) {
        return 0;
    }
    int total = L1 + L2 + L3;
    if (D > total) {
        printf("0\n"); // 每层嵌套至少吃掉一对括号
        return 0;
    }

    for (int i = 0; i <= L1; i++) {
        for (int j = 0; j <= L2; j++) {
            for (int k = 0; k <= L3; k++) {
                le[0][i][j][k] = (i == 0 && j == 0 && k == 0) ? 1 : 0;
            }
        }
    }

    for (int d = 1; d <= D; d++) {
        ll (*prev)[MAXL][MAXL] = le[d - 1]; // 深度不超过 d-1 的表
        ll (*cur)[MAXL][MAXL] = le[d];      // 深度不超过 d 的表
        cur[0][0][0] = 1;                   // 空串深度为 0
        for (int i = 0; i <= L1; i++) {
            for (int j = 0; j <= L2; j++) {
                for (int k = 0; k <= L3; k++) {
                    if (i == 0 && j == 0 && k == 0) {
                        continue;
                    }
                    ll t = 0;
                    // 首原子 (A)：内层只能含 ()，故内层用 prev[0][0][a]
                    for (int a2 = 0; a2 < k; a2++) {
                        t += cur[i][j][k - 1 - a2] * prev[0][0][a2];
                    }
                    // 首原子 [A]：内层不含 {}，故内层用 prev[0][a][b]
                    for (int a2 = 0; a2 < j; a2++) {
                        for (int b2 = 0; b2 <= k; b2++) {
                            t += prev[0][a2][b2] * cur[i][j - 1 - a2][k - b2];
                        }
                    }
                    // 首原子 {A}：三种括号都要在内层与剩余串间分配
                    for (int a2 = 0; a2 < i; a2++) {
                        for (int b2 = 0; b2 <= j; b2++) {
                            for (int c2 = 0; c2 <= k; c2++) {
                                t += prev[a2][b2][c2] * cur[i - 1 - a2][j - b2][k - c2];
                            }
                        }
                    }
                    cur[i][j][k] = t % MOD;
                }
            }
        }
    }

    // 深度恰为 D = 深度不超过 D 减去深度不超过 D-1
    ll ans;
    if (D == 0) {
        ans = le[0][L1][L2][L3];
    } else {
        ans = le[D][L1][L2][L3] - le[D - 1][L1][L2][L3];
    }
    ans %= MOD;
    if (ans < 0) {
        ans += MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

python

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#!/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 22:31
# update_at: 2026-10-01 22:38

import sys

MOD = 11380  # 题面里的“当前年份”，答案对它取余


def build_le(L1: int, L2: int, L3: int, D: int) -> list[list[list[list[int]]]]:
    """le[d][i][j][k]：深度不超过 d、含 i 对 {}、j 对 []、k 对 () 的 SS 串数。

    非空串唯一拆成「首原子 + 剩余部分」：首原子 = 第一个字符到它匹配的右括号。
    首原子内层深度必须 ≤ d-1（包裹加一层），剩余部分仍是 ≤ d 的 SS 串。
    """
    le = [[[[0] * (L3 + 1) for _ in range(L2 + 1)] for _ in range(L1 + 1)] for _ in range(D + 1)]
    for d in range(D + 1):
        le[d][0][0][0] = 1  # 空串深度为 0，对任何上界 d 都合法

    for d in range(1, D + 1):
        prev, cur = le[d - 1], le[d]
        for i in range(L1 + 1):
            for j in range(L2 + 1):
                for k in range(L3 + 1):
                    if i == j == k == 0:
                        continue  # 空串，上面已置 1
                    # 首原子 (A)：内层 A 只能含 ()，故内层用 prev[0][0][a]，剩余串拿走 k-1-a 对 ()
                    t = sum(cur[i][j][k - 1 - a] * prev[0][0][a] for a in range(k))
                    # 首原子 [A]：内层 A 不含 {}，故内层用 prev[0][a][b]，剩余的 {} 全给剩余串
                    t += sum(prev[0][a][b] * cur[i][j - 1 - a][k - b]
                             for a in range(j) for b in range(k + 1))
                    # 首原子 {A}：内层 A 无字符限制，三种括号都要在内层与剩余串间分配
                    t += sum(prev[a][b][c] * cur[i - 1 - a][j - b][k - c]
                             for a in range(i) for b in range(j + 1) for c in range(k + 1))
                    cur[i][j][k] = t % MOD
    return le


def solve() -> None:
    L1, L2, L3, D = map(int, sys.stdin.buffer.read().split())

    total = L1 + L2 + L3
    if D > total:
        print(0)  # 每层嵌套至少吃掉一对括号，深度不可能超过括号总对数
        return

    le = build_le(L1, L2, L3, D)
    # 深度恰为 D = 深度不超过 D 减去深度不超过 D-1；D = 0 时只有空串，无前一档
    ans = le[D][L1][L2][L3] - le[D - 1][L1][L2][L3] if D else le[0][L1][L2][L3]
    print(ans % MOD)


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：状态数 $O(D\cdot L_1L_2L_3)$ ，每个状态枚举分配 $O(L_1L_2L_3)$ ，合计 $O(D\cdot L_1^2L_2^2L_3^2)$ 。代入 $L\leqslant 10,\ D\leqslant 30$ ，最坏用例实测约 $8.6\times 10^6$ 次乘加。
空间复杂度： $O(D\cdot L_1L_2L_3)$ ，约 $31\times 11^3\approx 4\times 10^4$ 个整数。

总结

计数 DP 遇到 $\max$ 型合并时，把状态从「恰好」改成「不超过」，最后用差分还原恰好值。
序列型 SS 串用「首原子 + 剩余串」做唯一拆分，消除任意切分带来的重复计数。
题面规则 2–4 的「内部不含某类括号」直接体现为转移式中若干维固定为 $0$ 。

目录

形式化题目

正解

思路

卡点一：不能用「恰好」，要用「不超过」

卡点二：任选切分会重复计数

状态与转移

答案与边界

代码

复杂度

总结