括号上色

括号上色

小艺酱又得到了一堆括号。
括号是严格匹配的。
现在给括号进行上色。
上色有三个要求：
1、只有三种上色方案，不上色，上红色，上蓝色。
2、每对括号只有一个上色。
3、相邻的两个括号不能上相同的颜色，但是可以都不上色。
问括号上色有多少种方案？答案对1000000007取模。

输入描述：

输入括号序列s。(2<=|s|<=700)

输出描述：

输出方案数。

输入样例：

(())

输出样例：

12

代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define LL long long
const int mod=1000000007;

char s[1000];
int q[1000];
int mp[1000]={0};
int tot=1;
LL dp[1000][1000][3][3]={0};
int vis[1000][1000]={0};

int dfs(int L, int R)
{
    if(vis[L][R])
    {
        return 0;
    }
    vis[L][R]=1;
    if(R-L==1)
    {
        dp[L][R][1][0]=1, dp[L][R][2][0]=1;
        dp[L][R][0][1]=1, dp[L][R][0][2]=1;
        return 0;
    }
    if(mp[L]==R)
    {
        dfs(L+1, R-1);
        for(int u=0;u<3;u++)
        {
            for(int v=0;v<3;v++)
            {
                for(int x=0;x<3;x++)
                {
                    for(int y=0;y<3;y++)
                    {
                        if((u==0||v==0)&&(u!=0||v!=0)&&(u!=x||u+x==0)&&(v!=y||v+y==0))
                        {
                            dp[L][R][u][v]+=dp[L+1][R-1][x][y], dp[L][R][u][v]%=mod;
                        }
                    }
                }
            }
        }
    }
    else
    {
        dfs(L, mp[L]); dfs(mp[L]+1, R);
        for(int u=0;u<3;u++)
        {
            for(int v=0;v<3;v++)
            {
                for(int x=0;x<3;x++)
                {
                    for(int y=0;y<3;y++)
                    {
                        if((u==0||v==0)&&(u!=0||v!=0)&&(v!=x||v==0&&x==0))
                        {
                            dp[L][R][u][y]+=dp[L][mp[L]][u][v]*dp[mp[L]+1][R][x][y], dp[L][R][u][y]%=mod;
                        }
                    }
                }
            }
        }
    }
    
}

int main()
{
    int len,ans = 0;
    scanf("%s",s+1);
    len = strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        if(s[i]=='(')
        {
            q[tot++]=i;
        }
        else
        {
            mp[q[--tot]]=i;
        }
    }
    dfs(1, len);
    for(int u=0;u<3;u++)
    {
        for(int v=0;v<3;v++)
        {
            ans+=dp[1][len][u][v], ans%=1000000007;
        }
    }
    printf("%d",ans);
    return 0;
}