看了题解，虽然写法不一样时间复杂度应该是一个数量级的（可能常数大一点）。

哪位dalao能帮忙看看吗，第5个点就TLE了，蒟蒻被自己菜死了QAQ

#include <bits/stdc++.h>
#define DEBUG
using namespace std;
typedef int ll;
typedef unsigned long long ull;
ll read(){
	char c=getchar();bool flag=0;ll x=0;
	while(c<'0'||c>'9'){if(c=='-')flag=1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
	return flag?-x:x;
}
const ll N=7e2+10,mod=1e9+7;
ll stk[N],match[N],dp[N][N][3][3];// 0=noun 1=red 2=blue
char s[N];
void dfs(ll l,ll r){
	if(l==r-1){
		dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;
		return;
	}
//	dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;
	for(register ll i=l+1;i<=r-1;i=match[i]+1){
		dfs(i,match[i]); 
		if(i!=l+1){
			for(ll c1=0;c1<=2;c1++) for(ll c2=0;c2<=2;c2++) for(ll c3=0;c3<=2;c3++){
				dp[l+1][match[i]][c1][c3]+=dp[l+1][i-1][c1][c2]*dp[i][match[i]][0][c3]%mod;
				dp[l+1][match[i]][c1][c3]%=mod;
				if(c3==0){
					if(c2!=1) dp[l+1][match[i]][c1][0]+=dp[l+1][i-1][c1][c2]*dp[i][match[i]][1][0]%mod;
					dp[l+1][match[i]][c1][c3]%=mod;
					if(c2!=2) dp[l+1][match[i]][c1][0]+=dp[l+1][i-1][c1][c2]*dp[i][match[i]][2][0]%mod;
					dp[l+1][match[i]][c1][c3]%=mod;
				}
			}
		}
//		for(ll c1=0;c1<=2;c1++) for(ll c2=0;c2<=2;c2++){
//			printf("%lld %lld %lld %lld %lld\n",l+1,match[i],c1,c2,dp[l+1][match[i]][c1][c2]);
//		}
	}
	for(ll c1=1;c1<=2;c1++) for(ll c2=0;c2<=2;c2++) for(ll c3=0;c3<=2;c3++){
		if(c1!=c2) dp[l][r][c1][0]+=dp[l+1][r-1][c2][c3],dp[l][r][c1][0]%=mod;
		if(c1!=c3) dp[l][r][0][c1]+=dp[l+1][r-1][c2][c3],dp[l][r][0][c1]%=mod;
	}
//	for(ll c1=1;c1<=2;c1++){
//		printf("%lld %lld %lld %lld %lld\n",l,r,c1,0LL,dp[l][r][c1][0]);
//		printf("%lld %lld %lld %lld %lld\n",l,r,0LL,c1,dp[l][r][0][c1]);
//	}
}
int main(){
	scanf("%s",s+1);
	ll len=strlen(s+1),top=0;
	for(ll i=1;i<=len;i++){
		if(s[i]=='(') stk[++top]=i;
		else{
			match[stk[top]]=i,match[i]=stk[top];
			top--;
		}
	}
//	for(ll i=1;i<=len;i++) printf("%lld ",match[i]);cout<<endl;
	dfs(1,len);
	printf("%d",(dp[1][len][0][1]+dp[1][len][0][2]+dp[1][len][1][0]+dp[1][len][2][0])%mod);
}