因为这篇题解原文是用 Markdown 写成，在 我的博客 上面可能会有更好的阅读体验

考虑一个合法的括号序列长什么样子：(...) ，即由外面的括号和里面的部分组成，有用的信息来自于内部，于是我们关注内部可以由什么组成：

根据定义，一个合法的括号序列，内部可以是：S、AA、ASA、A、AS、SA，其中，AA 和 ASA 比较特殊，因为它们本身就是一个 A，信息被包含在 A 中。于是得到一个公式：

$$A_{i, j} = A_{i + 1, j - 1} + S_{i + 1, j - 1} + AS_{i + 1, j - 1} + SA_{i + 1, j - 1} \notag$$

接下来，我们考虑这些部分的信息如何维护：

1. 对于 A：我们若将这个递推公式深究到底，会得到什么？什么情况下就递归不下去了？也许最后的 A 是一个 ()，这当然合法，并且这个信息无法从别处递推来，于是，对于这个，我们在遇到的时候需要统计一下。或者，(S) 也是一个合法的括号序列，再往下深究，就是一个 S ，就是说，如果 (S) 放到上面的公式中，最后会得到一个 S 的值，显然这个值得是 $1$
2. 对于 S：经过上面的讨论，$\forall i, j \in \mathbb{N^+}, S_{i, j} = 1$ 而这个等式成立的前提是 $i, j$ 中间的部分完全由 '*' 组成

对于 AS，SA，ASA，AA 这些由 A 和 S 这两个比较基本的部分组成的部分，我们用乘法原理，可以求出它们的值。即：

$$AS_{i, j} = \sum_{i \le k \le j}A_{i, k} \times S_{k + 1, j} \notag \\ SA_{i, j} = \sum_{i \le k \le j}S_{i, k} \times A_{k + 1, j} \notag \\ ASA_{i, j} = \sum_{i \le k \le j}A_{i, k} \times SA_{k + 1, j} \notag \\ AA_{i, j} = \sum_{i \le k \le j}A_{i, k} \times A_{k + 1, j} \notag \\$$

需要注意的是，如果我们将 AA 和 ASA 的信息累加到 A 中，会导致原来的信息被覆盖掉，导致出错，所以在程序实现中我们需要用一个数组来备份合并操作之前的信息。

子任务1：测试点$1\sim 3$

$1\leq k\leq n\leq15$，显然可以使用搜索法。

枚举所有括号序列，判断其是否合法。

  1、连续的*不能超过k个。

  2、括号要匹配。

  3、SAS类型是非法括号序列。

时间复杂度O($N\times 3^N$),预计得分15分。

ps:可直接跳到子任务4。

子任务2：测试点$1\sim 13$

显然是一道区间DP问题。

首先明确，合法的括号序列应该是(),(S),(A),(SA),(AS),AA,ASA。

定义$d(l,r)$表示区间$[l,r]$的子串是合法括号序列的方案数。通过观察可以发现，$d(l,r)$可以由S序列转移得到，因此需要定义额外的状态，定义$s(l,r)$表示区间$[l,r]$能否构成合法的S型。

那么对于(),(S),(A),(SA),(AS)型，显然有：

 $d(l,r)=1$, ()型

 $d(l,r)+=1$, (S)型,$s(l+1,r-1)=1$

 $d(l,r)+=d(l+1,r-1)$, (A)型

 $d(l,r)+=d(l+tk+1,r-1)$, (SA)型,$1\leq tk\leq k,s(l+1,l+tk)=1$

 $d(l,r)+=d(l+1,r-tk-1)$, (AS)型,$1\leq tk\leq k,s(r-tk,r-1)=1$

对于AA、ASA型，需要枚举中间的分隔点$j(l\leq j\leq r)$：

 $d(l,r)+=d(l,j)*d(j+1,r)$, (AA)型

 $d(l,r)+=d(l,j)*d(j+tk+1,r)$, (ASA)型,$1\leq tk\leq k,s(j+1,j+tk)=1$

但是，对于部分括号序列，会出现重复计数，例如()()()会被识别成A|AA或者AA|A，()*()*()会被识别成AS|ASA或ASA|S|A。

为了避免重复计数，要求在合并时只能合并一次，因此定义状态$a(l,r)$表示单独的A类型，也即(),(S),(A),(SA),(AS)型，这些类型的特点是不能拆分。因此，状态转移方程需要做出如下修改：

 $a(l,r)=d(l,r)$,(),(S),(A),(SA),(AS)型

对于AA,ASA型，这是出现重复计数的类型：

 $d(l,r)+=a(l,j)*d(j+1,r)$, (AA)型

 $d(l,r)+=a(l,j)*d(j+tk+1,r)$, (ASA)型,$1\leq tk\leq k,s(j+1,j+tk)=1$

综上，算法的流程如下：

 1、预处理得出所有的$s(l,r)$。

 2、从小到大依次枚举每个区间$[l,r]$，求出相应的$d(l,r)$。

 3、最终的答案即为$d(1,n)$。

注意：在运算过程中需要不断对$10^9+7$取余。

注意：通过观察可以得出，首字符必是(，尾字符必是)，可以进行特殊处理。

时间复杂度O($N^4$)，预计得分65分。

子任务3：测试点$1\sim 15$

对于测试点$14\sim 15$,字符串中仅含？。那么状态$d(l_1,r_1+k)$和$d(l_2,r_2+k)$虽然表示的区间不同，但是结果必然是相同的。

因此，定义状态$f(i)$表示$i$个？构成的合法的序列的方案数。那么，状态转移方程修改为：

$f(1)=0$,一个?

$f(2)=1$,()型

$f(i)+=1$,(S)型

$f(i)+=f(i-2)$,(A)型

$f(i)=f(i-2-tk)$,(AS),(SA)型,$1\leq tk\leq k$

$f(i)=f(j)*f(i-j)$,AA型，$2\leq j\leq i - 2$

$f(i)=f(j)*f(i-j-tk)$,ASA型，$2\leq j\leq i-2,1\leq tk\leq k$

同样，也需要考虑重复计数的问题，定义$g(i)$表示单独的A类型的方案数。

那么状态转移方程需要做出部分修改：

$g(i)=f(i)$,()(S)(A)(SA)(AS)型

$f(i)=g(j)*f(i-j)$,AA型，$2\leq j\leq i - 2$

$f(i)=g(j)*f(i-j-tk)$,ASA型，$2\leq j\leq i-2,1\leq tk\leq k$

时间复杂度：O($N^3$),预计得分75分。

子任务4：测试点$1\sim 20$

显然是一道区间DP问题。

首先明确，合法的括号序列应该是(),(S),(A),(SA),(AS),AA,ASA。

定义$d(l,r)$表示区间$[l,r]$的子串是合法括号序列的方案数。通过观察可以发现，$d(l,r)$可以由非法括号序列转移得到，因此需要定义额外的状态。

  定义$s(l,r)$表示区间$[l,r]$能否构成合法的S型。

  定义$sa(l,r)$表示区间$[l,r]$的子串是SA型的方案数。

  定义$as(l,r)$表示区间$[l,r]$的子串是AS型的方案数。

那么对于(),(S),(A),(SA),(AS)型，显然有：

  $d(l,r)=1$, ()型

  $d(l,r)+=s(l+1,r-1)$, (S)型

  $d(l,r)+=d(l+1,r-1)$, (A)型

  $d(l,r)+=sa(l+1,r-1)$, (SA)型

  $d(l,r)+=as(l+1,r-1)$, (AS)型

对于AA、ASA型，需要枚举中间的分隔点$j(l\leq j\leq r)$：

  $d(l,r)+=d(l,j)*d(j+1,r)$, (AA)型

  $d(l,r)+=d(l,j)*sa(j+1,r)$, (ASA)型

同时需要维护AS,SA型，同样需要枚举中间的分隔点$j(l\leq j\leq r)$：

  $as(l,r)+=d(l,j)*s(j+1,r)$, (AS)型

  $sa(l,r)+=s(l,j)*d(j+1,r)$, (SA)型

但是，对于部分括号序列，会出现重复计数，例如()()()会被识别成A|AA或者AA|A，()*()*()会被识别成AS|ASA或ASA|S|A。

为了避免重复计数，要求在合并时只能合并一次，因此定义状态$a(l,r)$表示单独的A类型，也即(),(S),(A),(SA),(AS)型，这些类型的特点是不能拆分。

因此，状态转移方程需要做出如下修改：

  $a(l,r)=d(l,r)$,(),(S),(A),(SA),(AS)型

对于AA,ASA型，这是出现重复计数的类型：

  $d(l,r)+=a(l,j)*d(j+1,r)$, (AA)型

  $d(l,r)+=a(l,j)*sa(j+1,r)$, (ASA)型

综上，算法的流程如下：

  1、预处理得出所有的$s(l,r)$。

  2、从小到大依次枚举每个区间$[l,r]$，求出相应的$d(l,r),a(l,r),sa(l,r),sa(l,r)$。

  3、最终的答案即为$d(1,n)$。

注意：在运算过程中需要不断对$10^9+7$取余。

注意：通过观察可以得出，首字符必是(，尾字符必是)，可以进行特殊处理。

时间复杂度O($N^3$)，预计得分100分。