http://codeforces.com/problemset/problem/149/D
题意：
给一个给定括号序列，给该括号上色，上色有三个要求
1、只有三种上色方案，不上色，上红色，上蓝色
2、每对括号必须只能给其中的一个上色
3、相邻的两个不能上同色，可以都不上色
求0-len-1这一区间内有多少种上色方案
思路：dp[l][r][i][j]表示从l到r的长度且左右括号分别是i j的方案数
那么转移方程：
1：l+1=r时， dp[l][r][0][1]=1;
dp[l][r][1][0]=1;
dp[l][r][0][2]=1;
dp[l][r][2][0]=1;
2：s[l]和s[r]匹配时，dp[l][r][0][1]=(dp[l][r][0][1]+dp[l+1][r-1][i][j])
dp[l][r][1][0]=(dp[l][r][1][0]+dp[l+1][r-1][i][j])
dp[l][r][0][2]=(dp[l][r][0][2]+dp[l+1][r-1][i][j])
dp[l][r][2][0]=(dp[l][r][2][0]+dp[l+1][r-1][i][j])
3:不匹配时，dp[l][r][i][j]=(dp[l][r][i][j]+dp[l][p][i][k]*dp[p+1][r][q][j]);
且s[l]和s[p]匹配
//#pragma comment(linker, "/STACK:167772160")//手动扩栈~~~~hdu 用c++交
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <algorithm>
#include <vector>
// #include<malloc.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define LL long long
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
const double pi = acos(-);
const LL mod = 1e9+;
const int N = ;
// inline int r(){
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
// return x*f;
// }
LL dp[N][N][][];
int match[N];
char s[N];
LL ans;
int len;
int tem[N]; void init(){
int p;
p=;
for(int i=;i<len;i++){
if(s[i]=='(') tem[p++]=i;
else {
match[i]=tem[p-];
match[tem[p-]]=i;
p--;
}
}
} void dfs(int l,int r){
if(l==r-){
dp[l][r][][]=;
dp[l][r][][]=;
dp[l][r][][]=;
dp[l][r][][]=;
return;
}
else if(match[l]==r){
dfs(l+,r-);
for(int i=;i<;i++){
for(int j=;j<;j++){
if(j!=)
dp[l][r][][]=(dp[l][r][][]+dp[l+][r-][i][j])%mod;
if(i!=)
dp[l][r][][]=(dp[l][r][][]+dp[l+][r-][i][j])%mod;
if(j!=)
dp[l][r][][]=(dp[l][r][][]+dp[l+][r-][i][j])%mod;
if(i!=)
dp[l][r][][]=(dp[l][r][][]+dp[l+][r-][i][j])%mod;
}
}
return;
}
else{
int p=match[l];
dfs(l,p);
dfs(p+,r);
for(int i=;i<;i++){
for(int j=;j<;j++){
for(int k=;k<;k++){
for(int q=;q<;q++){
if(!((k==&&q==)||(k==&&q==))){
dp[l][r][i][j]=(dp[l][r][i][j]+(dp[l][p][i][k]*dp[p+][r][q][j])%mod)%mod;
}
}
}
}
}
return;
}
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%s",s);
len=strlen(s);
// printf("%d\n",len);
init();
dfs(,len-);
ans=;
for(int i=;i<;i++){
for(int j=;j<;j++){
ans=(ans+dp[][len-][i][j])%mod;
}
}
printf("%I64d\n",ans);
return ;
}