本文于 2023.03.26 大修（近半重写）

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

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

题意

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

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

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

  2. 并列型： ABAB ，ASBASB

显然合法的括号序列两端必然分别是左右括号，而且合法的括号序列最小长度为2。

初步分析

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

这道题一看就像是区间DP。设状态 f[i][j]f[i][j] 表示 [i,j][i,j] 这段区间内的数量，由于上文已经证明看出“合法的括号序列两端必然分别是左右括号”，所以需要先确保 ii 对应位置可以为 (,即 a[i] == '(' || a[i] == '?'，对 jj 也同理，不满足的话 f[i][j]f[i][j] 一律为 0。后文的讨论均基于 i,ji,j 满足要求的情况。

按照刚刚上面的分类进行讨论，记 s[i][j]s[i][j] 表示 [i:j][i:j] 能否完全由不超过 k 个连续的 * 或者 ? 组成，或者说 s[i][j]s[i][j] 表示 a[i][j]a[i][j] 能否构成题目中的 S。则可列出方程：

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

（放在逗号右面表示只有当满足这个条件时才计算）

(AS)(AS) 只要枚举一下 S 就行，pp 为 A 的右端点（包含）：

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

(SA)(SA) 与 (AS)(AS) 差不多，留作习题答案略。那么包含型的情况已经讨论完了。

下面是并列型的情况。在计算 ASBASB 的贡献的时候，如果像我们刚刚那样设计状态就会列出错误的方程：

f[i][j]+=∑p=i+1j−2∑q=p+1j−1f[i][p]×f[q][j], s[p+1][q−1]=truef[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

这个式子即枚举 AA 的右端点 pp 和 BB 的左端点 qq（均包含）来间接枚举 S=a[p+1:q−1]S=a[p+1:q-1]，从而转移 ASBASB，这里 S 能取空所以可以连 AB 的情况一起处理。

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

()()??()

有以下几种情况：

cnt A S B ASB
1 () null ()()() ()()()()
2 () null ()**() ()()**()
3 ()() null ()() ()()()()
4 ()() null **() ()()**()
5 ()() ** () ()()**()
6 ()()() null () ()()()()

显然算重了（由于在计算子区间 AA 和 BB 的并列型情况时还会有重复，所以按这种错误方法算出的情况数不止上述 6 种）。

去重

如果每次在左边的 AA 只枚举包含型，不枚举并列型的结构，而 BB 包含型与并列型都枚举，这样每种拆法就只会数一次了。后文将这种拆法表示为 FS?BFS?B（?? 表示可有可无）。由于 FS?BFS?B 没法再拆成其他的并列型，所以显然不会重复，下面简要证明不会遗漏：

一种并列型的 AA 总能表示为 A=F+S′?+B′A = F+S'?+B'，其中 FF 为包含型，B′B' 任意，情况 A+S?+B=F+S′?+B′S?BA+S?+B = F+S'?+B'S?B，符合 FS?BFS?B，故能够被计数。

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

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

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

g[i][j]=∑p=i+1j−2∑q=p+1j−1f[i][p]×(f[q][j]+g[q][j]), s[p+1][q−1]=trueg[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

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

1
2
3
4
5
6
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;
    }
}

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

优化

复杂度瓶颈在 ASBASB 的 O(n4)O(n^4) 上，所以观察 ASBASB 的式子，此时先把 ii 和 jj 当做定值。

后面的 f[i][p]f[i][p] 的值与 qq 无关，因此我们可以把 f[i][p]f[i][p] 从最内层的求和里提出来。

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

只关注内层的循环，这时如何优化就明显一些了——前缀和。

我们设一个新数组 hh：

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

若忽略 ss 的条件，最内层循环等于 h[j−1]−h[p]h[j-1] - h[p]。

再考虑 ss，由于最内层循环在递增的是 pp 而 qq 并不变化——作为条件的区间 ss 是左端点不动向右延伸的——我们可以预处理出每一个位置往后延伸的 * 或者 ? 的最长的长度，记为 b[i]b[i]，则从 p+1p+1 点最远能延伸到的下标为 p+1+b[i]p+1+b[i]。所以我们就可以在每次循环 ii 的时候预处理 hh 数组的值，用 h[min(j,p+b[p+1]+1)]−h[p]h[min(j, p+b[p+1]+1)] - h[p] 代替原来最内层的求和了。

因为 ll 递增，所以不用担心 f[q][j]f[q][j]、f[q][j]f[q][j] 还没有求（这两个区间肯定比正在求的小）。

（其实建议预处理时直接处理出向后延伸到的最大下标，应该会方便一点，但我懒得改了）

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <algorithm>
#include <cstdio>

using namespace std;

constexpr int maxn = 550;
constexpr int MOD = 1'000'000'007;

using ull = unsigned long long;
using ll = long long;

int normal(ll x)
{
    int rst = x % MOD;
    if (rst < 0) rst += MOD;
    return rst;
}

// 计算模意义下可变个数的参数的和，用法： add(...)

template <typename T>
int add(T x)
{
    return normal(x);
}

template <typename T, typename... Ts>
int add(T x, Ts... args)
{
    return normal(x + add(args...));
}

int mul(int a, int b)
{
    return normal(ll(a) * ll(b));
}

int n, k;
char a[maxn];
int f[maxn][maxn];   // 包含型，后用 F 代替
int g[maxn][maxn];   // 并列型，后用 G 代替
bool s[maxn][maxn];  // a[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]) f[i][j] = 1;  // (S)

            f[i][j] = add(f[i][j], 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], 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], 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], f[p][j], g[p][j]);
            }

            for (int p = i + 1; p <= j - 2; p++) {
                g[i][j] = add(g[i][j], normal(mul(f[i][p], add(h[min(j, p + b[p + 1] + 1)], -h[p]))));
            }
        }
    }

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

    return 0;
}