codeforces149D

发表于 | 分类于 | 阅读数 次

链接:codeforces149D

题解

  • 区间l~r可以划分为l~mach[l] mach[l]+1~r,dfs一下分类处理就好
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(regitser int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int p=1e9+7;
    const int N=800;
    ll dp[N][N][3][3],ans;
    int mach[N],tmp[N],n,cnt;
    char str[N+1];
    inline void init(){
    	scanf("%s",str+1);n=strlen(str+1);
    	rep(i,1,n)if(str[i]=='(')tmp[++cnt]=i;else if(str[i]==')')mach[tmp[cnt--]]=i;
    }
    ll dfs(int l,int r){
    	if(r==l+1)return dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;
    	if(mach[l]==r){
    		dfs(l+1,r-1);
    		rep(i,0,2)rep(j,0,2){
    			if(j!=1)dp[l][r][0][1]=(dp[l][r][0][1]+dp[l+1][r-1][i][j])%p;
    			if(j!=2)dp[l][r][0][2]=(dp[l][r][0][2]+dp[l+1][r-1][i][j])%p;
    			if(i!=1)dp[l][r][1][0]=(dp[l][r][1][0]+dp[l+1][r-1][i][j])%p;
    			if(i!=2)dp[l][r][2][0]=(dp[l][r][2][0]+dp[l+1][r-1][i][j])%p;
    		}
    	}
    	else {
    		dfs(l,mach[l]);
    		dfs(mach[l]+1,r);
    		rep(i,0,2)rep(j,0,2)rep(x,0,2)rep(y,0,2){
    			if(x&&x==y)continue;
    			dp[l][r][i][j]=(dp[l][r][i][j]+dp[l][mach[l]][i][x]*dp[mach[l]+1][r][y][j]%p)%p;
    		}
    	}
    }
    int main(){
    	init();
    	dfs(1,n);
    	rep(i,0,2)rep(j,0,2)ans=(ans+dp[1][n][i][j])%p;
    	printf("%d\n",ans);
    	return 0;
    }