题目链接：https://vjudge.net/problem/CodeForces-149D#author=algo11318030
题意：给定一个括号序列，对这个括号序列进行染色，有以下要求：每个字符有三种情况：不染色，染成红色，染成蓝色；每对匹配的括号，有且仅有一个字符被染色；所有相邻的两个字符，不能染成同一种颜色。求染色的方案数
这题一开始想用递推写，后来发现不太写的出来。网上查了一下，基本都是用dfs的形式写的，到现在也不知道有没有递推的写法。设f[l][r][0/1/2][0/1/2]表示从i到j的括号，i不染色/染成红色/染成蓝色的方案数。dfs的过程中，主要依据括号的匹配来递归。有如下几种情况：
1. r-l=1,这是dfs的边界，且由过程2和3可得l,r是一对匹配的括号，则有f[l][r][0][1]=f[l][r][1][0]=f[l][r][0][2]=f[l][r][2][0]=1;
2. l和r是一对匹配的括号，则由相邻括号不同色，且匹配的括号有且仅有一个字符被染色，递归区间(l+1,r-1)，则有
f[l][r][0][1]=f[l+1][r-1][0][2]+f[l+1][r-1][2][0]
f[l][r][0][2]=f[l+1][r-1][1][0]+f[l+1][r-1][2][0]
f[l][r][1][0]=f[l+1][r-1][0][2]+f[l+1][r-1][2][0]
f[l][r][2][0]=f[l+1][r-1][0][1]+f[l+1][r-1][1][0]
3. l和r不是一对匹配的括号，则找到l的匹配的括号m[l]（这可以由一个预处理得出），分别递归区间(l,m[l])和(m[l]+1,r)，最后根据乘法原理求出:f[l][r][i][j]+=Σf[l][m[l]][i][k]*f[m[l]+1][r][t][j]),0<i,j,k,t<3，k=0或t=0或k!=t
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
ll f[710][710][3][3];
int m[710],n,i,j;
string s;
void dp(int l,int r){
if (l+1==r){ //*
f[l][r][0][1]=f[l][r][1][0]=f[l][r][0][2]=f[l][r][2][0]=1;
return;
}
if (m[l]==r){
dp(l+1,r-1); //*
for (int i=0;i<3;i++)
for (int j=0;j<3;j++){
if (j!=1) f[l][r][0][1]=(f[l][r][0][1]+f[l+1][r-1][i][j])%mod;
if (i!=1) f[l][r][1][0]=(f[l][r][1][0]+f[l+1][r-1][i][j])%mod;
if (j!=2) f[l][r][0][2]=(f[l][r][0][2]+f[l+1][r-1][i][j])%mod;
if (i!=2) f[l][r][2][0]=(f[l][r][2][0]+f[l+1][r-1][i][j])%mod;
}
}
else {
dp(l,m[l]); dp(m[l]+1,r); //*
for (int i=0;i<3;i++)
for (int j=0;j<3;j++)
for (int k=0;k<3;k++)
for (int t=0;t<3;t++)
if (!(t!=0&&k!=0&&k==t))
f[l][r][i][j]=(f[l][r][i][j]+f[l][m[l]][i][k]*f[m[l]+1][r][t][j])%mod; //*
}
}
int main(){
cin>>s; n=s.length();
for (i=0;i<n;i++)
if (s[i]=='('){
int cnt=1;
for (j=i+1;j<n;j++){
if (s[j]=='(') cnt++; else cnt--;
if (cnt==0) break;
}
m[i]=j;
}
dp(0,n-1);
ll ans=0;
for (i=0;i<3;i++)
for (j=0;j<3;j++) ans=(ans+f[0][n-1][i][j])%mod;
cout<<ans<<endl;
return 0;
}