题意翻译

给出一个配对的括号序列，之后对该序列按以下方法进行染色：

  • 一个括号可以染红色、蓝色或不染色
  • 一对匹配的括号必须且只能将其中一个染色
  • 相邻两个括号颜色不能相同（但可以都不染色）

请求出符合条件的染色方案数，对 $10^9 + 7$ 取模

输入格式

输入仅有一行，包含一个字符串 $|s|$ ，表示给定的括号序列

输出格式

输出仅有一行，包含一个整数，表示符合条件的方案数对 $10^9 + 7$ 取模的结果

Input & Output ‘s examples

Input ‘s eg 1

(())

Output ‘s eg 1

12

Input ‘s eg 2

(()())

Output ‘s eg 2

40

Input ‘s eg 3

()

Output ‘s eg 3

4

数据范围与约定

设 $|s|$ 为输入括号序列的长度

对于 $100\%$ 的数据，保证 $1 \leq |s| \leq 700$，且保证 $s$ 括号匹配。

分析

题目中长度 $\leq 700$ 的数据范围基本在暗示两维以上的数组，且输入的是一个括号序列，不难想到区间 $\text{dp}$。

采用区间 $\text{dp}$ 的老套路，设 $f[l][r]$ 表示从 $l$ 到 $r$ 的范围内符合条件的方案数。

但这样不好处理相同颜色不可相邻的问题，考虑增加维度。设 $f[l][r][0/1/2][0/1/2]$ 表示从 $l$ 到 $r$ 中最左边染为无色/红色/蓝色，右边同理的方案数。

之后预处理每个左括号对应的右括号位置，这可以用一个栈辅助实现。

考虑转移。观察一下，可以发现每个合法的括号序列可以被拆解为更小的合法序列，比如 ()() 就可以拆解为两个 ()。

因此，我们采用记忆化搜索的方式，将整个括号序列拆解为若干小序列进行计算。

之后进行讨论，当 $l + 1 = r$ 时，则整个括号序列为 () ，此时有

若 $r$ 正好是 $l$ 的对应位置，则 $\lbrack l + 1 , r - 1 \rbrack$ 也是一对合法的括号序列，递归处理 $\lbrack l + 1 , r - 1 \rbrack$。

之后考虑 $l$ 与 $r$ 的颜色，可得

否则的话，我们将括号序列划分成两段，依次处理之后根据乘法原理相乘累加即可。

剩下的细节见代码即可。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define PII pair<int , int>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

typedef long long ll;
typedef unsigned long long ull;

template <class T>
inline void read(T &x) {
    char c = getchar(), f = 0; x = 0;
    while (!isdigit(c)) f = (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    x = f ? -x : x;
}

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 1000000007;

char a[M];
ll f[750][750][3][3] , dy[M];

void dfs(int l , int r){
    if(l + 1 == r) {
        f[l][r][0][1] = f[l][r][0][2] = f[l][r][1][0] = f[l][r][2][0] = 1;
        return ; 
    }
    if(dy[l] == r){
        dfs(l + 1 , r - 1);
        rep(i , 0 , 2){
            rep(j , 0 , 2){
                if(i != 1) f[l][r][1][0] += f[l + 1][r - 1][i][j] , f[l][r][1][0] %= HA;
                if(j != 1) f[l][r][0][1] += f[l + 1][r - 1][i][j] , f[l][r][0][1] %= HA;
                if(i != 2) f[l][r][2][0] += f[l + 1][r - 1][i][j] , f[l][r][2][0] %= HA;
                if(j != 2) f[l][r][0][2] += f[l + 1][r - 1][i][j] , f[l][r][0][2] %= HA;
            }
        }
    }
    else{
        dfs(l , dy[l]);
        dfs(dy[l] + 1 , r);
        rep(i , 0 , 2){
            rep(j , 0 , 2){
                rep(k , 0 , 2){
                    rep(d , 0 , 2){
                        if((j == 0 && k == 0) || (j != k)){
                            f[l][r][i][d] += f[l][dy[l]][i][j] * f[dy[l] + 1][r][k][d] % HA;
                            f[l][r][i][d] %= HA;
                        }
                    }
                }
            }
        }
    }
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    scanf("%s" , a + 1);
    int len = strlen(a + 1);
    stack<int> s;
    rep(i , 1 , len){
        if(a[i] == '(') s.push(i);
        else{
            dy[s.top()] = i;
            s.pop();
        }
    }
    dfs(1 , len);
    ll res = 0;
    rep(i , 0 , 2){
        rep(j , 0 , 2){
            res += f[1][len][i][j] , res %= HA;
        }
    }
    printf("%lld\n" , res);
	
    return 0;
}

THE END