D. Coloring Brackets

预处理

由于栈的特性，我们可以储存左括号和读取到刚刚读到的左括号，并当读取到右括号时，我们可以将最近的左括号提取出来并做一个匹配处理。

DP的设置

DP数组的设置，dp[l][r][color1][color2]表示的是l位置是color1和r位置是color2的方案数。

第一种情况，当l和r是匹配的关系，即左括号对上了对应的右括号，那么我们就可以以根据题目的条件提前确定color1和color2的内容，就是一者没有上任何的颜色，另一者上了蓝色或者红色，而这一共有四种可能，因而我们要考虑四个状态的转移，而由于l和r是先确定的，我们可以进而去考虑l+1和r-1所构成的区间，并注意题目给的的限制条件（相邻的括号不能上同样的颜色）

第二种情况，不是第一种情况的情况。

由于提前处理了，可以很方便得到l所对应上的r，因而我们可以先处理一部分已经完成匹配的括号对，然后再假装从这个括号对后面的部分，注意这个设计要保证是没有任何疏漏，不能放过区间上任何一个括号。因而，我们可以这么分，l到l所对应的r的部分，l所对应的r的部分再到区间末端这两个部分（l所对应的r的部分再到区间末端这两个部分的这一部分，由于dfs的特性，会被相同不断操作，从而保障了区间内全部的点全部被操作一遍）。

对了，上述这些只是一种思路或者说是dp的一种大体的框架。

我们还要考虑到边界的书写，

我们的做法是不断将这些区间进行压缩，压缩的最终结果肯定会发生的情况是两个括号直接黏在一起，而这也会对应第一种情况内的那四种方案，换句话说这种边界的处理相当于是第一种情况的特例。

代码

#include <bits/stdc++.h>
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define pi acos(-1.0)
#define PII pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define MAX 1000005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
using namespace std;
int n,m;
int dp[701][701][3][3],link[701];
stack<int > pos;
void dfs(int l,int r)
{
	if(r==l+1)
	{
		dp[l][r][0][2]=1;
		dp[l][r][0][1]=1;
		dp[l][r][2][0]=1;
		dp[l][r][1][0]=1;
	}   
	else if(link[l]==r)
	{
		dfs(l+1,r-1);
        repd(p,0,2)
		    repd(q,0,2)
			{
			    if(q!=2) dp[l][r][0][2] = (dp[l][r][0][2]+dp[l+1][r-1][p][q])%MOD;   	
		        if(q!=1) dp[l][r][0][1] = (dp[l][r][0][1]+dp[l+1][r-1][p][q])%MOD; 
		        if(p!=2) dp[l][r][2][0] = (dp[l][r][2][0]+dp[l+1][r-1][p][q])%MOD; 
		        if(p!=1) dp[l][r][1][0] = (dp[l][r][1][0]+dp[l+1][r-1][p][q])%MOD; 
			}	    
	}
	else
	{
		dfs(l,link[l]);dfs(link[l]+1,r);
		ll res=0;
		repd(i,0,2)
		    repd(j,0,2)
		        repd(p,0,2)
		            repd(q,0,2)
		                if( !((p==q)&&(p==1||p==2)) ) 
		                  dp[l][r][i][j] = (dp[l][r][i][j]+dp[l][ link[l] ][i][p]*dp[ link[l] + 1 ][r][q][j])%MOD;
	}
}
int main()
{
	MEM(dp,0);
	string s;
	cin>>s;
	ll len = s.length(),ans=0;
	//predo
	rep(i,0,len)
	{
		if(s[i]=='(')
	       pos.push(i+1);
	    else
	    {
	    	link[ pos.top() ] = i+1;
			link[ i+1 ] = pos.top();
			pos.pop(); 
		}
	}
	
	dfs(1,len);
	repd(i,0,2)
	    repd(j,0,2)
	        ans=(ans+dp[1][len][i][j])%MOD;
	cout<<ans;
    return 0;
}

人生中第一道紫题（好像是）

其他

Each bracket is either not colored any color, or is colored red, or is colored blue.

either......or......是指列举出来的条件只有一个是成立的。

colored + 颜色名，被染上某种颜色

每一个括号要么被没涂上任何的颜色，要么上了红色，要么就是上了蓝色。

For any pair of matching brackets exactly one of them is colored. In other words, for any bracket the following is true: either it or the matching bracket that corresponds to it is colored.

一对中的一个括号才有颜色。

and vice versa 反之亦然