Luogu P7914 [CSP-S 2021] 括号序列
本题解思路十分暴力。
Semi-formed Idea
根据题目描述，符合要求的括号序列可以分成两类
- 包含型：$()$，$(A)$，$(S)$，$(AS)$，$(SA)$
- 并列型：$AA$，$ASA$
于是我们就可以开始逐一枚举这几种情况并统计答案了！
对于 $()$，$(A)$ 和 $(S)$，我们可以直接进行判断。
对于 $(AS)$，$(SA)$，$AA$ 和 $ASA$，我们可以枚举一个断点，把中间的地方拆成两部分（对于 $ASA$，拆成 $A$ 和 $SA$ 两部分，同时维护一下 $SA$，便只需枚举一个断点就可以计算答案贡献了）。
这样我们在程序中需要枚举左断点 $l$ 与右端点 $r$，维护 $S[l][r]$，$A[l][r]$，$SA[l][r]$（$S[l][r]$ 表示 $[l, r]$ 这一段符合 $S$ 的方案数，其它两个同理）就可以算出答案了！
时间复杂度为 $\mathcal{O}(n^3)$（枚举 $l$ 一个 $n$，枚举 $r$ 一个 $n$，枚举断点一个 $n$）。
Hack and Debug
这样打的话会激动地发现只有第一个样例 AC 了。
原因如下：
我们处理并列型的时候，是枚举在 $[l, r]$ 中的断点进行判断的，但是当我们遇到这样的序列：
\[()()()\]在 $2$，$3$ 之间断开会发现 $[1, 2]$ 符合 $A$，$[3, 6]$ 符合 $A$；
在 $4$，$5$ 之间断开会发现 $[1, 4]$符合 $A$，$[5, 6]$ 符合 $A$；
于是这一个串就贡献了两次答案。
$ASA$ 同理，例如 $()()()$ 以同样的方法统计也会贡献两次答案。
那我们该解决呢？
我们可以在枚举 $AA$ 的断点的时候，判断前一个 $A$ 为全部的符合要求的 $A$ ，而后一个 $A$ 为包含型的 $A$ （之后我们称包含型 $A$ 为 $_A$），即 $A_A$。
我们来模拟一遍：
\[()()()\]当我们在 $2$，$3$ 之间断开的话，$[1, 2]$ 符合 $A$，但 $[3, 6]$ 不符合 $_A$；
当我们在 $4$，$5$ 之间断开的话， $[1,4]$ 符合 $A$，$[5, 6]$ 符合 $_A$，计入一次贡献；
这样这个串就只贡献了一次答案，符合要求。
更多的 $()$ 同样只会贡献一次答案，$ASA$ 转化为 $AS_A$ 后也同样只会贡献一次了。
可能有同学要问了，为什么不需要排除 $_A$ 呢？
原因很好想，因为 $_A$ 从中间断开后就不是合法的括号序列了，因此不会被重复计算贡献。
于是，我们产生贡献的括号序列就变成了这些：$()$，$(S)$，$(A)$，$(AS)$，$(SA)$，$A_A$，$AS_A$。
需要维护的数组有：$S[l][r]$，$A[l][r]$，$_A[l][r]$，$S_A[l][r]$。