问题：给你一个长度为n的合法括号序列，你要对每一对括号的其中一个半括号（必须并且只能为一个）染色，有两种颜色可以选择。要求染完色后，序列里不存在相邻的位置是同种颜色的（两个都未染色的算合法）。求一共有几种染色方案。答案取模1e9+7。

思路: 区间dp。记dp[l][r][i][j]为对区间[l,r],s[l]染颜色i,s[r]染颜色j时的合法方案有几种。（1<=l<=r<=n,0<=i<=2,0<=j<=2）这里0表示未染色,1,2分别代表颜色1和颜色2。

　　我们用栈可以O(n)的预处理出每一个位置i上的半括号与它匹配的另一半在哪个位置记为match[i]。
因为题目染色条件的限制。
当l===r时，dp[l][r][][]显然为0。
当r=l+1时，只有 1 0,2 0,0 1,0 2。这四种方案时合法的。所以dp[l][r][1][0]=dp[l][r][2][0]=dp[l][r][0][1]=dp[l][r][0][2]=1,其他都为0。
当r>l+1且l和r正好是一对匹配括号时。就递归找[l+1,r-1]的合法方案。
当l和r不是一对匹配括号时。就递归找[l,match[l]],[match[l]+1,r]这两个区间。总的染色方案就等于这两个子区间的合法方案相乘。
因为颜色的约束，具体状态转移见代码，挺好理解的。
如果我没算错的话，这道题的做法时间复杂度应该是O(n)的。

AC代码：

//#include<bits/stdc++.h>
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
#define pb push_back
#define X first
#define Y second
inline ll gcd(ll a, ll b) { while (b != 0) { ll c = a % b; a = b; b = c; }return a < 0 ? -a : a; }
inline ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
inline ll lowbit(ll x) { return x & (-x); }
const double PI = 3.14159265358979323846;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
inline char nc() {
    static char buf[1 << 21], * p1 = buf, * p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
inline ll rd() {
    //#define getchar nc
    ll x = 0, f = 1; char ch = getchar();
    while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
const double eps = 1e-6;
const int M = 1e6 + 10;
const int N = 1e5 + 10;
ll dp[710][710][3][3];
int match[710];
char s[N];
int n;
void dfs(int l, int r) {
    if (l == r) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                dp[l][r][i][j] = 0;
            }
        }
        return;
    }
    if (l + 1 == r) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == j || (i > 0 && j > 0))dp[l][r][i][j] = 0;
                else dp[l][r][i][j] = 1;
            }
        }
    }
    else if (match[l] == r) {
        dfs(l + 1, r - 1);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++)dp[l][r][i][j] = 0;
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (j != 1)dp[l][r][0][1] = (dp[l][r][0][1] + dp[l + 1][r - 1][i][j]) % mod;
                if (j != 2)dp[l][r][0][2] = (dp[l][r][0][2] + dp[l + 1][r - 1][i][j]) % mod;
                if (i != 1)dp[l][r][1][0] = (dp[l][r][1][0] + dp[l + 1][r - 1][i][j]) % mod;
                if (i != 2)dp[l][r][2][0] = (dp[l][r][2][0] + dp[l + 1][r - 1][i][j]) % mod;
            }
        }
    }
    else {
        dfs(l, match[l]), dfs(match[l] + 1, r);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++)dp[l][r][i][j] = 0;
        }
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                for (int x = 0; x < 3; x++) {
                    for (int y = 0; y < 3; y++) {
                        if ((y == 0 && x == 0) || (x != y)) {
                            dp[l][r][i][j] = (dp[l][r][i][j] + dp[l][match[l]][i][x] * dp[match[l] + 1][r][y][j] % mod) % mod;
                        }
                    }
                }
            }
        }
    }
}
int sta[N];
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int p = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(')sta[++p] = i;
        else {
            match[sta[p]] = i;
            match[i] = sta[p];
            p--;
        }
    }
    dfs(1, n);
    ll ans = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            ans += dp[1][n][i][j];
            ans %= mod;
        }
    }
    cout << ans << endl;
}