VIII.CF149D Coloring Brackets

考虑设\(f[i][j][k=0/1/2][l=0/1/2]\)表示：将区间\([i,j]\)里的东西染色，左端染上颜色\(k\)，右端染上颜色\(l\)（\(0\)为红，\(1\)为蓝，\(2\)不染）的方案数。

因为这个\(n\)是\(700\)，\(n^3\)似乎过不了，考虑\(n^2\)的区间DP。

我们首先关于每个括号找出它匹配的位置。然后，约定只有合法的子串（连续的）的DP值是有效的，不合法的子串的DP值都为\(0\)。

当我们要求出\([i,j]\)的DP值时，

1. 如果在位置\([i,j]\)上的括号本身就是匹配的，直接从\([i+1,j-1]\)转移过来；

2. 否则，既然这个子串是合法的，那唯一的构成方式就是拼接（例如()()）。直接从某个位置断开（比如说从右边界的匹配位置那边断开）拼一起即可。

复杂度为\(O((C+1)^4*n^2)\)，其中\(C\)是颜色数（本题中为\(2\)）。

代码:

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int mat[710],n,f[710][710][3][3],res;
char s[710];
stack<int>stk;
int main(){
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;i++){
		if(s[i]=='(')stk.push(i);
		else mat[stk.top()]=i,mat[i]=stk.top(),stk.pop();
	}
	for(int i=1;i<n;i++)if(mat[i]==i+1)f[i][i+1][0][2]=f[i][i+1][2][0]=f[i][i+1][1][2]=f[i][i+1][2][1]=1;
	for(int l=4;l<=n;l+=2)for(int i=1,j=i+l-1;j<=n;i++,j++){
		if(s[i]!='('||s[j]!=')')continue;
		if(mat[i]==j){
			for(int a=0;a<3;a++)for(int b=0;b<3;b++){
				if(a==b)continue;
				if(a!=2&&b!=2)continue;
				for(int c=0;c<3;c++)for(int d=0;d<3;d++){
					if(a!=2&&c!=2&&a==c)continue;
					if(b!=2&&d!=2&&b==d)continue;
					(f[i][j][a][b]+=f[i+1][j-1][c][d])%=mod;
				}
			}
		}else{
			int k=mat[j];
			for(int a=0;a<3;a++)for(int b=0;b<3;b++)for(int c=0;c<3;c++)for(int d=0;d<3;d++){
				if(b!=2&&c!=2&&b==c)continue;
				f[i][j][a][d]=(1ll*f[i][k-1][a][b]*f[k][j][c][d]+f[i][j][a][d])%mod;
			}		
		}
	}
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)(res+=f[1][n][i][j])%=mod;
	printf("%d\n",res);
	return 0;
}