Rt

记录详情

$code:$

#include<iostream>
#include<stack>
#define int long long
#define sfor(i, h, t) for(int i = (h); i <= (t); ++i)
const int MAXL = 0x2C0;
const int P = 0x3B9ACA07;
using namespace std;
stack <int> stk;
int bracket[MAXL >> 1];
int dp[MAXL][MAXL][3][3], ans;
void dfs(int l, int r){
    #ifdef DEBUG
    cout << l << " " << r << ":\n";
    #endif
    if(l + 1 == r){
        dp[l][r][0][1] = dp[l][r][0][2] = dp[l][r][1][0] = dp[l][r][2][0] = 1;
        #ifdef DEBUG
        cout << "1 1 1 1\n";
        #endif
        return;
    }
    if(bracket[l] == r){
        dfs(l + 1, r - 1);
        sfor(p, 0, 2)
            sfor(q, 0, 2){
                if(p != 1)
                    (dp[l][r][1][0] += dp[l + 1][r - 1][p][q]) %= P;
                if(p != 2)
                    (dp[l][r][2][0] += dp[l + 1][r - 1][p][q]) %= P;
                if(q != 1)
                    (dp[l][r][0][1] += dp[l + 1][r - 1][p][q]) %= P;
                if(q != 2)
                    (dp[l][r][0][2] += dp[l + 1][r - 1][p][q]) %= P;
            }
    }
    else{
        dfs(l, bracket[l]);
        dfs(bracket[l] + 1, r);
        sfor(p, 0, 2)
            sfor(q, 0, 2)
                sfor(p_, 0, 2)
                    sfor(q_, 0, 2)
                        if(q != p_ || !q)
                            (dp[l][r][p][q_] += dp[l][bracket[l]][p][q] * dp[bracket[l] + 1][r][p_][q_]) %= P;
    }
    #ifdef DEBUG
    cout << dp[l][r][0][1] << " " << dp[l][r][0][2] << " " << dp[l][r][1][0] << " " << dp[l][r][2][0] << endl;
    #endif
}
signed main(){
    ios::sync_with_stdio(false);
    char c;
    int N = 0;
    while((cin >> c) && ++N){
        if(c == '(')
            stk.push(N);
        else{
            bracket[N] = stk.top();
            bracket[stk.top()] = N;
            stk.pop();
        }
    }
    #ifdef DEBUG
    sfor(i, 1, N)
        cout << bracket[i] << endl;
    cout << stk.size() << endl;;
    #endif
    dfs(1, N);
    sfor(p, 0, 2)
        sfor(q, 0, 2)
            (ans += dp[1][N][p][q]) %= P;
    cout << ans << endl;
    return 0;
}