本文首先发布于个人博客，博客园不定期更新。推荐去我的博客阅读，效果更佳。

因为 csp-s 考的太惨了，所以一直想着回头把前三题都AC了，结果一拖拖到现在才做完（

还有就是动态规划好难（wtcl)

题意

本题题意较复杂，建议直接去看原题（题目链接）

总的来说，合法的括号序列一共分两类：

1. 包含型：()， (A)，(S)，(AS)，(SA)

2. 并列型： AB ，ASB

很容易发现合法的括号序列两端必然分别是左右括号，而且合法的括号序列最小长度为2

初步分析

数据范围可知这题大概需要一个 \(O(n^3)\) 的方法

这道题一看就是区间DP（假如你不知道什么是区间DP就先去学一下，等以后再看这篇文章吧）

第一直觉估计都是状态 \(f[i][j]\) 表示 \([i,j]\) 这段区间内的数量，然后转移方程也都比较好想，例如：

\[\left. \begin{array} { l } { (A):f [ i ] [ j ] += f[i+1][j-1] } \\ { (S):f[i][j] += 1,\space s[i+1][j-1]=true } \\ \end{array} \right. \]

( \(s[i][j]\) 表示 \([i:j]\) 能否完全由不超过 k 个连续的 * 或者 ? 组成，放在逗号右面表示只有当满足这个条件时才计算）

(AS) 只要枚举一下 S 就行（ \(p\) 为 A 的右端点）：

\[{ (AS):f[i][j] += \sum_{p=i+2}^{j-1}f[i][p],\space s[p+1][j-1]=true } \]

(SA) 与 (AS) 差不多就不再提了。

但是在计算 ASB 的贡献的时候，像我们刚刚那样设计状态就会列出错误的方程（ \(p\) 为 A 的右端点）：

\[f[i][j]+=\sum_{p=i+1}^{j-2}\sum_{q=p+1}^{j-1} f[i][p]\times f[q][j],\space s[p+1][q-1]=true \]

这个式子可以理解成枚举 A 的右端点 \(p\) 和 B 的左端点 \(q\) 来间接枚举 S ，从而转移 ASB，做个特判就可以连 AB 一起处理了。

但是这样的转移方程为什么是错的呢，我们看下面这样的括号序列：

()()()

当你在枚举到 A = [1:2] 时会计算一遍这种情况，而 A = [1:4] 的时候又会被计算一遍

于是你发现你算重了。

去重

所以我们要想别的办法来避免算重。比较容易想到的就是我每次在左边的 A 只枚举包含型的结构，也就是说在刚刚的例子中枚举 A 只会枚举 [1:2] = () 这种包含型的，而不会枚举 [1:4] = ()() 这种并列型的，这样你每种拆法就会只被计算一次了。

重新设计一下状态，\(f[i][j]\) 表示该区间内包含型序列的数量，\(g[i][j]\) 表示并列型序列的数量。

重新看一下原来的转移方程，你会发现 (A)，(S) 的转移方程根本不需要改，(AS) 的转移方程只是把后面的 \(f[i][p]\) 改成 \(f[i][p]+g[i][p]\) 即可

仿照原来的思路，ASB 的转移方程如下：

\[g[i][j] = \sum_{p=i+1}^{j-2}\sum_{q=p+1}^{j-1} f[i][p] \times (f[q][j]+g[q][j]),\space s[p+1][q-1] = true \]

代码如下：（为了清晰直观，删去取余的过程）

for(int p=i+1; p <= j-2; p++){
    for(int q=p+1; q <= j-1; q++){
        if(s[p+1][q-1] || q == p+1) g[i][j] += (ULL)f[i][p] * (f[q][j] + g[q][j]);
        else break;
    }
}

按这个思路写对了应该就能拿到 65pts 了，现在离 AC 还差一个优化

优化

性能的瓶颈全都在 ASB 的 \(O(n^4)\) 上，所以观察 ASB 的式子，此时 \(i\) 和 \(j\) 都可以当做定值。

后面的 \(f[q][j]+g[q][j]\) 的值与 \(p\) 无关，因此我们可以把 \(f[i][p]\) 从最内层的 \(\sum\) 里提出来。

所以现在只考虑内层的 \(\sum\)：

\[\sum_{q=p+1}^{j-1}(f[q][j]+g[q][j]),\space s[p+1][q-1] = true \]

这时如何优化就很容易想到了：前缀和

我们设一个新数组 \(h\)，先不去考虑 * 的条件：

\[h[p]=\sum_{t=i+2}^{p}f[t][j]+g[t][j] \]

我们可以在读入之后预处理出每一个位置往后延伸的 * 或者 ? 的最长的长度，记为 \(b[i]\)

每次循环 \(i\) 的时候预处理 \(h\) 数组的值，因为 \(l\) 递增循环所以不用担心 \(f[q][j]\) 还没有求的问题，这样我们可以用 \(h[min(j, p+b[p+1]+1)] - h[p]\) 代替原来的内层的 \(\sum\)（其实建议预处理时直接处理出向后延伸的最大下标，应该会方便一点，但我懒得改了）

最终代码（代码丑，请见谅）：

#include 
#include 
using namespace std;

const int maxn = 550;
const int MOD = 1000000007;

typedef unsigned long long ULL;

int inline add(int a, int b){
    return (a%MOD + b%MOD) % MOD;
}

int n, k;
char a[maxn];
int f[maxn][maxn]; // (...),  后面注释里用 F 代替
int g[maxn][maxn]; // (...)...(...) 用 G 代替
bool s[maxn][maxn]; // s[i][j] 表示能否构成连续的而且 个数不超过 k 的 *
int h[maxn], b[maxn];

int main(){

    scanf("%d%d", &n, &k);
    scanf("%s", a+1);

    for(int i=1; i <= n; i++){
        int j;
        for(j=i; j <= n && j-i+1 <= k; j++){
            if(a[j] == '*' || a[j] == '?') s[i][j] = true;
            else break;
        }
        b[i] = j-i;
    }

    for(int l=2; l <= n; l++){
        for(int i=1; i+l-1 <= n; i++){
            int j = i+l-1;

            if(a[i] != '(' && a[i] != '?' || a[j] != ')' && a[j] != '?') continue;

            if(i+1 == j){ // 单独一对括号 ()
                f[i][j] = 1;
                continue;
            }

            if(s[i+1][j-1] && l-2 <= k) f[i][j] = 1; // (S)

            f[i][j] = add(f[i][j], add(f[i+1][j-1], g[i+1][j-1])); // (F) 或 (G), 对应题目要求的 (A)

            for(int p=i+1; p < j-1; p++){ // (SF) 或 (SG), 对应 (SA)
                if(s[i+1][p]) f[i][j] = add(f[i][j], add(f[p+1][j-1], g[p+1][j-1])); 
                else break;
            }

            for(int p=j-1; p > i+1; p--){ // (FS) 或 (GS), 对应 (AS)
                if(s[p][j-1]) f[i][j] = add(f[i][j], add(f[i+1][p-1], g[i+1][p-1])); 
                else break;
            }

            // AB 或者 ASB

            h[i+1] = 0; // 前缀和优化
            for(int p=i+2; p <= j; p++){ 
                h[p] = add(h[p-1], add(f[p][j], g[p][j]));
            }

            for(int p=i+1; p <= j-2; p++){
                // 一定要注意加一个MOD, 我之前没写查了半天没找到错在哪
                g[i][j] = add(g[i][j], (ULL)f[i][p] * ((ULL)MOD + h[min(j, p+b[p+1]+1)] - h[p]) % MOD); 
            }
        }
    }

    printf("%d", add(f[1][n], g[1][n]));

    return 0;
}