Codeforces

Luogu

分析

设 $dp_{l,r,0/1/2,0/1/2}$ 表示 $[l,r]$ 段，$l$ 没有颜色/红色/蓝色、$r$ 没有颜色/红色/蓝色的方案数。

当 $r-l+1=2$ 时为边界，有 $dp_{l,r,1,0}=dp_{l,r,2,0}=dp_{l,r,0,1}=dp_{l,r,0,2}=1$。

考虑转移。

• 如果 $l,r$ 是一对匹配的括号，直接从 $dp_{l+1,r-1,x,y}$ 转移过来即可。
• 否则，$[l,r]$ 是由若干段匹配的括号序列组成的，随便找一个位置断开然后转移即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=700+10;
const int mod=1e9+7;
void add(int& x,int y) { x=(x+y)%mod; }

int n; char s[N];
int sta[N],top=0,m[N];

int dp[N][N][3][3];
void dfs(int l,int r) {
    if (r-l+1==2) {
        dp[l][r][1][0]=dp[l][r][0][1]=dp[l][r][2][0]=dp[l][r][0][2]=1;
        return;
    }
    if (m[r]==l) {
        dfs(l+1,r-1);
        for (int i=0;i<=2;++i)
            for (int j=0;j<=2;++j) {
                if (i!=1) add(dp[l][r][1][0],dp[l+1][r-1][i][j]);
                if (i!=2) add(dp[l][r][2][0],dp[l+1][r-1][i][j]);
                if (j!=1) add(dp[l][r][0][1],dp[l+1][r-1][i][j]);
                if (j!=2) add(dp[l][r][0][2],dp[l+1][r-1][i][j]);
            }
    } else {
        dfs(l,m[r]-1),dfs(m[r],r);
        for (int i=0;i<=2;++i)
            for (int j=0;j<=2;++j)
                for (int p=0;p<=2;++p)
                    for (int q=0;q<=2;++q) {
                        if (j&&j==p) continue;
                        add(dp[l][r][i][q],1ll*dp[l][m[r]-1][i][j]*dp[m[r]][r][p][q]%mod);
                    }
    }
}

int main() {
    scanf("%s",s+1),n=strlen(s+1);
    for (int i=1;i<=n;++i) {
        if (s[i]=='(') sta[++top]=i;
        else m[i]=sta[top],--top;
    }
    dfs(1,n); int ans=0;
    for (int i=0;i<=2;++i)
        for (int j=0;j<=2;++j)
            ans=(ans+dp[1][n][i][j])%mod;
    printf("%d\n",ans);
    return 0;
}