解题思路

算法设计

采用记忆化搜索（记忆化DFS）解决括号组合计数问题：

状态定义

• 四维状态数组：f[a][b][c][d]表示剩余a个'{}'、b个"[]"、c个"()"，且深度≤d时的合法组合数
• 边界条件：
  • 当a=b=c=0时，f[a][b][c][d]=1（空字符串）
  • 当d=0时，f[a][b][c][0]=0（深度为0时无解）

递推关系

实现步骤

1. 初始化：设置边界条件
2. 记忆化搜索：
   • 枚举最外层括号类型
   • 分解为左右子问题
   • 根据乘法原理计算方案数
3. 结果处理：最终结果为f[a][b][c][d]-f[a][b][c][d-1]（精确深度d的方案数）

复杂度分析

• 时间复杂度：O(a*b*c*d)，通过记忆化避免重复计算
• 空间复杂度：O(a*b*c*d)，用于存储状态数组

注意事项

• 需要使用long long类型存储大数结果
• 注意处理边界条件
• 最终结果需要减去低一层的方案数

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <map>
#include <stack>
#include <cmath>

using namespace std;
const int p = 11380;
int a, b, c, d, dp[15][15][15][35];

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1)+(x << 3)+(ch ^ 48);
        ch = getchar();
    }
    return x*f;
}

int search(int aa, int bb, int cc, int dd) {
    int ans = 0;
    if (!dd && (aa | bb | cc)) return 0;
    if (!(aa|bb|cc)) return dp[aa][bb][cc][dd] = 1;
    if (dp[aa][bb][cc][dd]) return dp[aa][bb][cc][dd];
    for (int i = 0; i <= cc; i++) {
        if (i) ans = (ans+search(0, 0, i-1, dd-1) % p * search(aa, bb, cc-i, dd) % p) % p;
        for (int j = 0; j <= bb; j++) {
            if (j) ans = (ans+search(0, j-1, i, dd-1) % p * search(aa, bb-j, cc-i, dd) % p) % p;
            for (int k = 1; k <= aa; k++)
                ans = (ans+search(k-1, j, i, dd-1) % p*search(aa-k, bb-j, cc-i, dd) % p) % p;
        }
    }
    return dp[aa][bb][cc][dd] = ans;
}
int main() {
	a = read(); b = read(); c = read(); d = read();
    search(a, b, c, d);
	if(d) search(a, b, c, d-1);
    int ans = dp[a][b][c][d]-(d?dp[a][b][c][d-1]:0);
    printf("%d", (ans+p)%p);
    return 0;
}