详细题解

题意重述

给定一个正确括号序列 $s$，长度 $|s| \le 700$。
对括号进行涂色，每个括号可以：

• 不涂色（记为颜色 $0$）
• 涂红色（记为颜色 $1$）
• 涂蓝色（记为颜色 $2$）

要求：

1. 每对匹配的括号中，恰好一个被涂色（即不能两个都涂，也不能两个都不涂）。
2. 相邻的涂色括号颜色不能相同（未涂色的括号不参与相邻颜色比较）。
3. 求所有合法的涂色方案数，对 $10^9+7$ 取模。

---

符号约定

• 颜色：$0$（未涂色）、$1$（红）、$2$（蓝）。
• 一对匹配括号 $(l, r)$ 中：
  一个涂色（$1$ 或 $2$），另一个为 $0$。
  所以一对括号的合法颜色组合共有 $4$ 种：
  $(0,1), (0,2), (1,0), (2,0)$。

---

思路分析

括号序列是正确括号序列，可以递归分解为：

• 一个最外层括号对 $(l, r)$，内部可能包含若干直接嵌套的括号序列（即与 $(l, r)$ 紧邻的第一层子括号对）。

例如：( ( ) ( ( ) ) )
最外层 $(0,6)$，内部直接子括号对：$(1,2)$ 和 $(3,5)$。

这种结构天然适合区间 DP。

---

状态定义

设 $dp[l][r][c_l][c_r]$ 表示：
区间 $[l, r]$ 是一个匹配的括号对（即 $s[l] =$ (，$s[r] =$ )，且它们匹配），
且 $l$ 的颜色固定为 $c_l$，$r$ 的颜色固定为 $c_r$，
在此条件下，区间内部（$l+1$ 到 $r-1$ 之间的子括号序列）的所有合法涂色方案数。

注意：

• $c_l, c_r \in \{0,1,2\}$
• 必须满足 $(c_l, c_r)$ 是合法配对（恰好一个非 $0$，且相邻颜色限制暂时不跨区间检查）。

---

内部子问题处理

对于区间 $(l, r)$，内部可能包含若干个直接子括号对，它们之间由字符隔开（例如 ()() 中的两个 () 之间没有嵌套关系）。

设内部第一个直接子括号对为 $(l+1, m)$，其中 $m$ 是 $l+1$ 的匹配位置。
那么区间 $[l, r]$ 的内部结构可以表示为：

(  [子对1]  [子对2] ... [子对k]  )
l  l+1      ...         r-1   r

子对之间是并列关系，不是嵌套。
每个子对内部又是一个完整的匹配括号对，因此可以用 $dp$ 递归求解。

---

关键技巧：合并相邻子对

对于并列的子对 $(p_1, q_1), (p_2, q_2), \dots, (p_k, q_k)$，
相邻子对之间没有括号直接相邻（因为正确括号序列中，)( 不会出现）。
但是，前一个子对的右括号与后一个子对的左括号在原始字符串中是相邻的字符吗？
不一定，例如 (())() 中，第一个子对 $(1,2)$ 的右括号 $s[2]$ 与第二个子对 $(3,4)$ 的左括号 $s[3]$ 是相邻的，因此它们必须满足相邻涂色括号颜色不同。

所以我们需要在合并子对时考虑边界颜色冲突。

---

辅助 DP：合并子对序列

定义 $f[i][c]$：
考虑前 $i$ 个直接子对（按顺序排列），并且第 $i$ 个子对的右括号颜色为 $c$ 时，前 $i$ 个子对内部的所有合法涂色方案数。

初始化：
$f[0][c_l] = 1$，表示还没有子对时，只有左括号 $l$ 的颜色固定为 $c_l$。

转移：
假设第 $i$ 个子对是 $(x, y)$，它的左括号颜色为 $c_x$，右括号颜色为 $c_y$。
在合并时，我们需要检查：

1. $(c_x, c_y)$ 必须是合法配对（一个为 $0$，另一个非 $0$）。
2. 如果 $i \ge 1$，那么第 $i-1$ 个子对的右括号颜色 $c_{prev}$ 与第 $i$ 个子对的左括号颜色 $c_x$ 不能都是非 $0$ 且相等（相邻涂色括号颜色不同）。
3. 第 $i$ 个子对内部的所有涂色方案数由 $dp[x][y][c_x][c_y]$ 给出。

因此转移为：

$$f[i][c_y] \ += f[i-1][c_{prev}] \times dp[x][y][c_x][c_y] $$

其中 $c_{prev}$ 遍历所有可能的颜色（$0,1,2$），并满足颜色冲突规则。

---

最终 $dp[l][r][c_l][c_r]$ 的计算

当内部子对处理完后，我们得到 $f[k][c_{last}]$，其中 $k$ 是内部子对个数，$c_{last}$ 是最后一个子对右括号的颜色。

此时还要检查：

• 最外层右括号 $r$ 的颜色 $c_r$ 与最后一个子对右括号颜色 $c_{last}$ 是否相邻（它们之间可能隔着 $l$ 和 $r$ 本身？ 注意：在字符串中，$r$ 紧跟在最后一个子对之后吗？ 不一定。
  实际上，对于最外层 $(l, r)$，内部子对最后一个右括号的位置是 $r-1$ 吗？ 不一定，因为可能有 ( ( ) ( ) ) 这种，最后一个子对 $(4,5)$ 的右括号 $s[5]$ 紧挨着 $s[6]$（最外层右括号），所以必须检查 $c_{last}$ 与 $c_r$ 是否冲突：
  如果 $c_{last} \neq 0$ 且 $c_r \neq 0$ 且 $c_{last} = c_r$，则非法。

此外，最外层左括号 $l$ 的颜色 $c_l$ 与第一个子对左括号颜色 $c_{x1}$ 是否相邻？
在字符串中，$l$ 后面紧跟着 $l+1$，即第一个子对的左括号，所以也要检查 $c_l$ 与 $c_{x1}$ 不能同时非 $0$ 且相等。

因此：

1. 如果内部没有子对（$k=0$），那么 $l+1 = r$，即 () 这种情况。
   此时要求 $(c_l, c_r)$ 合法即可，没有内部冲突。
2. 否则，需要检查：
   • $c_l$ 与第一个子对左括号颜色不冲突。
   • $c_{last}$ 与 $c_r$ 不冲突。

然后：

$$dp[l][r][c_l][c_r] = \sum_{合法组合} f[k][c_{last}]$$

---

实现细节

• 预处理每个括号的匹配位置 match[i]（栈即可）。
• 按区间长度从小到大枚举 $l, r$，只处理 $s[l] =$ ( 且 $s[r] =$ ) 且 match[l] = r 的情况。
• 内部子对提取：从 $l+1$ 开始，不断用 match[pos] 跳到子对结尾，然后 pos = match[pos] + 1。
• 转移时枚举 $c_l, c_r, c_x, c_y$ 等，共 $3^4 = 81$ 种组合，但大部分不合法，可优化。
• 最终答案：最外层是整个序列，假设它对应 $(0, n-1)$，则答案为：

$$\sum_{c_l, c_r \ \text{合法}} dp[0][n-1][c_l][c_r]$$

---

时间复杂度

区间数 $O(n^2)$，每个区间内部子对个数 $O(n)$，颜色枚举常数 $O(1)$，总复杂度 $O(n^3)$。
但 $n \le 700$ 时 $O(n^3)$ 勉强可过，实际标程通过精细实现可达 $O(n^2)$ 常数倍。

---

样例验证

样例 1：(())

• 最外层 $(0,3)$，内部只有一个子对 $(1,2)$。
• 枚举 $c_0, c_3, c_1, c_2$，保证 $(0,3)$ 合法，$(1,2)$ 合法，且 $c_0$ 与 $c_1$ 不冲突，$c_2$ 与 $c_3$ 不冲突。
• 计算得 $12$。

样例 2：(()())

• 最外层 $(0,5)$，内部两个子对 $(1,2)$ 和 $(3,4)$。
• 合并子对时需处理相邻颜色冲突。
• 结果 $40$。

样例 3：()

• 最外层 $(0,1)$，内部无子对。
• 直接 $(c_0, c_1)$ 合法即可，共 $4$ 种。

---

核心代码框架（伪代码）

const int MOD = 1e9 + 7;
int n, match[705];
long long dp[705][705][3][3];
string s;

void solve() {
    // 预处理 match
    stack<int> st;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') st.push(i);
        else {
            int l = st.top(); st.pop();
            match[l] = i;
            match[i] = l;
        }
    }

    // 区间 DP
    for (int len = 2; len <= n; len += 2) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            if (s[l] != '(' || s[r] != ')' || match[l] != r) continue;

            // 提取直接子对
            vector<pair<int, int>> children;
            int pos = l + 1;
            while (pos < r) {
                int nxt = match[pos];
                children.push_back({pos, nxt});
                pos = nxt + 1;
            }

            // 枚举 l, r 的颜色
            for (int cl = 0; cl < 3; cl++) {
                for (int cr = 0; cr < 3; cr++) {
                    if ((cl == 0) == (cr == 0)) continue; // 必须恰好一个非0

                    if (children.empty()) {
                        // 情况：()
                        dp[l][r][cl][cr] = 1;
                        continue;
                    }

                    // 辅助 DP 合并子对
                    long long f[705][3] = {0};
                    // 初始化：第0个子对之前
                    int firstL = children[0].first, firstR = children[0].second;
                    for (int cx = 0; cx < 3; cx++) {
                        for (int cy = 0; cy < 3; cy++) {
                            if ((cx == 0) == (cy == 0)) continue;
                            if (cl != 0 && cx != 0 && cl == cx) continue; // 与最外层左括号冲突
                            f[0][cy] = (f[0][cy] + dp[firstL][firstR][cx][cy]) % MOD;
                        }
                    }

                    // 依次合并后续子对
                    for (int i = 1; i < children.size(); i++) {
                        int L = children[i].first, R = children[i].second;
                        for (int prevC = 0; prevC < 3; prevC++) {
                            if (f[i-1][prevC] == 0) continue;
                            for (int cx = 0; cx < 3; cx++) {
                                for (int cy = 0; cy < 3; cy++) {
                                    if ((cx == 0) == (cy == 0)) continue;
                                    if (prevC != 0 && cx != 0 && prevC == cx) continue;
                                    f[i][cy] = (f[i][cy] + f[i-1][prevC] * dp[L][R][cx][cy]) % MOD;
                                }
                            }
                        }
                    }

                    // 最后检查最后一个子对右括号与最外层右括号冲突
                    int last = children.size() - 1;
                    for (int lastC = 0; lastC < 3; lastC++) {
                        if (f[last][lastC] == 0) continue;
                        if (lastC != 0 && cr != 0 && lastC == cr) continue;
                        dp[l][r][cl][cr] = (dp[l][r][cl][cr] + f[last][lastC]) % MOD;
                    }
                }
            }
        }
    }

    // 答案
    long long ans = 0;
    for (int cl = 0; cl < 3; cl++) {
        for (int cr = 0; cr < 3; cr++) {
            if ((cl == 0) == (cr == 0)) continue;
            ans = (ans + dp[0][n-1][cl][cr]) % MOD;
        }
    }
    cout << ans << endl;
}

---

总结

本题利用括号序列的递归结构 + 区间 DP，在状态中同时记录区间两端颜色，并通过辅助 DP 合并并列子对，处理相邻颜色冲突。时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$，$n \le 700$ 时可通过。