题意：给定一个长度为 \(n\) 的括号串 \(S\)（不一定合法），求有多少种长度为 \(m\) 的不同括号串 \(T\)，存在一种将 \(T\) 划分为两个子序列 \(A, B\) 的方式，使得 \(S=A\)，\(B\) 为合法括号串。
考虑如何判定 \(T\) 能否划分，贪心枚举 \(T\) 的每一位，能给 \(A\) 就给，否则交给 \(B\)。
但是有可能遇到 \(B\) 中已经没有左括号给当前的右括号匹配了，考虑撤销掉一些 \(A\)，将单个左括号加上一个合法串构成的子串交给 \(B\)，此时右括号可以匹配。
由判定设计 dp 状态：\(f_{i, j, k}\) 表示有 \(i\) 个匹配给 \(A\)，\(B\) 中目前有 \(j\) 个左括号和 \(k\) 个右括号。
按贪心判定法转移最终每种合法情况的转移路径都是唯一确定的，可以做到不重不漏。
代码：（此处 \(n + 2t = m\)，01 串 0 为左括号 1 为右括号）
for (int i = 1, j, c; i <= n; i++) {for (j = i, c = 0; j && ~c; j--) {c += s[j] == '1' ? 1 : -1;pre[i] = j;}if (~c) pre[i] = 0;
}
f[0][0][0] = 1;
for (int j = 0; j <= t; j++) {for (int k = 0; k <= j; k++) {for (int i = 0; i <= n; i++) {int x = f[i][j][k];if (i < n) add(f[i + 1][j][k], x);if (i == n || s[i + 1] == '1') add(f[i][j + 1][k], x);if (i == n || s[i + 1] == '0') add(f[i][j][k + 1], x);if ((i == n || s[i + 1] == '0') && j == k && pre[i]) {int d = (i - pre[i]) / 2 + 1;if (j + d <= t) add(f[pre[i] - 1][j + d][k + d], x);}}}
}
cout << f[n][t][t] << "\n";