记录编号	574892	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CSP 2021S]括号序列	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	1.748 s
提交时间	2022-08-28 12:35:20	内存使用	5.48 MiB

#include <bits/stdc++.h> 

using i64 = long long;

const int N = 510, M = 5, MOD = 1e9 + 7;
int n, m;
char c[N];
i64 a[M][N][N];
// 0 a 1 s 2 as 3 sa 4 bak

bool eq(int idx, char ch) { return c[idx] == ch || c[idx] == '?'; }

int main() {
    freopen("2021bracket.in", "r", stdin); 
    freopen("2021bracket.out", "w", stdout);
    std::cin >> n >> m >> c + 1;
    for (int i = 1; i <= n; ++ i) 
        for (int j = i; j <= n && j - i + 1 <= m; ++ j) 
            if (!eq(j, '*')) break;
            else a[1][i][j] = 1;
    for (int len = 2; len <= n; ++ len) 
        for (int i = 1; i <= n - len + 1; ++ i) {
            int j = i + len - 1;
            if (eq(i, '(') && eq(j, ')')) { // (...)
                if (len == 2) a[0][i][j] = 1;
                else a[0][i][j] = (a[0][i][j] + a[0][i + 1][j - 1]) % MOD,
                     a[0][i][j] = (a[0][i][j] + a[1][i + 1][j - 1]) % MOD,
                     a[0][i][j] = (a[0][i][j] + a[2][i + 1][j - 1]) % MOD,
                     a[0][i][j] = (a[0][i][j] + a[3][i + 1][j - 1]) % MOD;
            }
            a[4][i][j] = a[0][i][j];
            for (int k = i; k <= j; ++ k) // merge
                a[0][i][j] = (a[0][i][j] + a[4][i][k] * a[0][k + 1][j]) % MOD, // aa
                a[2][i][j] = (a[2][i][j] + a[0][i][k] * a[1][k + 1][j]) % MOD, // as
                a[3][i][j] = (a[3][i][j] + a[1][i][k] * a[0][k + 1][j]) % MOD, // sa
                a[0][i][j] = (a[0][i][j] + a[4][i][k] * a[3][k + 1][j]) % MOD; // asa
        }
    std::cout << a[0][1][n] << '\n';
    return 0;
}