Title Link

https://codeforces.com/problemset/problem/149/D

meaning of the title

Give a matching bracket string. Each bracket can be dyed a and b or not. Requirements:

• Each matching bracket needs to have and only one coloring
• Adjacent brackets shall not be dyed in the same color, but neither

Number of dyeing schemes

thinking

Note that we are given a string that has been matched. In this string, the matching object of each bracket has been set. Therefore, when we get an interval, we don't want to guess the matching scheme like making legal bracket matching numbers, but dye the fixed scheme.

For interval l-r, there are two possibilities:

• If l-r is a match, then its scheme number should be inherited from the scheme number of L + 1 and R-1.
• If l-r is not a match, then there must be and only one position K for rk to match and l k-1 to match. Then the number of schemes should be the sum of the product of each case in two intervals.

We use four-dimensional dp[l][r][i][j]. Represents the dyeing I on the left and dyeing j on the right in the interval l to r, and ij takes 0 as colorless. If it is scheme 1 mentioned above, then (ignoring one and two dimensions) is that 0 1 is inherited from j not 1, and 1 0 is inherited from I not 1... And so on, but pay attention to lr matching. dp[l][r][0][0] in this illegal case, the answer is 0.

If it is scheme 2, we will enumerate four variables i1, j1, i2 and j2. dp[l][r][i1][j2] is added by all legal dp[l][k-1][i1][j1]*dp[k][r][i2][j2]. Note here that what we mean by legality means that j1 and i2 cannot be dyed the same color at the same time.

Let's talk about scheme 2. Since we are sure that K Matches r and l matches k-1, can we eliminate some invalid schemes, such as i2=j2=0? Of course, but as long as we assign the appropriate initial value, the correctness of the answer will not be wrong. It is not cost-effective to make the code messy in order to improve the efficiency (or even add a pile of judgment).

As for the initial value, let's go through a linear traversal, and let the legal case of dp[i][i+1] when I matches i+1 be 1 (1 0,2 0,0 1,0 2), and the rest be 0.

The final answer is to sum all values of dp[1][n]. Note that all values do not necessarily match 1-n.

code

#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long
//#define double long double
using namespace std;
	typedef long long ll;
	const int maxn=705;
	const int inf=0x3f3f3f3f;
    const int mod=1000000007;
	int n,m,k;
    int a[maxn];
    int ans;
    int dp[maxn][maxn][3][3];
    string s;
    int match[maxn];
    inline int pls(int a,int b){
        return (a+b)%mod;
    }
    inline int mul(int a,int b){
        return (a*b)%mod;
    }
	signed main(){
        IOS

		#ifndef ONLINE_JUDGE
		    freopen("IO\\in.txt","r",stdin);
		    freopen("IO\\out.txt","w",stdout);
        #endif
		int tn=1;
        cin>>s;
        n=s.size();
        s='0'+s;
        stack<int>sa;
        for(int i=1;i<=n;i++){
            if(s[i]=='(')   sa.push(i);
            else{
                match[i]=sa.top();
                match[sa.top()]=i;
                sa.pop();
            }
        }
        for(int i=1;i<n;i++){
            if(match[i]==i+1)
                dp[i][i+1][0][1]=dp[i][i+1][0][2]=dp[i][i+1][1][0]=dp[i][i+1][2][0]=1;
        }
        for(int len=2;len<=n;len++){
            for(int l=1;l+len-1<=n;l++){
                int r=l+len-1;
                if(match[l]==r){//Yes, the answer is all legal constructs
                    for(int t1=0;t1<3;t1++)
                        for(int t2=0;t2<3;t2++){
                            if(t2!=1)   dp[l][r][0][1]=pls(dp[l][r][0][1],dp[l+1][r-1][t1][t2]);    
                            if(t2!=2)   dp[l][r][0][2]=pls(dp[l][r][0][2],dp[l+1][r-1][t1][t2]);    
                            if(t1!=1)   dp[l][r][1][0]=pls(dp[l][r][1][0],dp[l+1][r-1][t1][t2]);    
                            if(t1!=2)   dp[l][r][2][0]=pls(dp[l][r][2][0],dp[l+1][r-1][t1][t2]);    
                        }
                }
                else{
                    int k=match[r];
                    for(int t1=0;t1<3;t1++)
                        for(int t2=0;t2<3;t2++)
                            for(int t3=0;t3<3;t3++)
                                for(int t4=0;t4<3;t4++){
                                    if(!((t3==t4)&&t3))
                                        dp[l][r][t1][t2]=pls(dp[l][r][t1][t2],mul(dp[l][k-1][t1][t3],dp[k][r][t4][t2]));
                                }
                }
            }
        }
        int ans=0;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                ans=pls(ans,dp[1][n][i][j]);
        cout<<ans%mod<<endl;
	}