Coloring Brackets

Created by LXC on Wed May 24 15:36:27 2023

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

ranting: 1900

tag: dp

problem

给出一个合法括号序列（每个左括号都有对应的右括号）
现在你需要给这个括号序列涂上颜色。

涂色的规则:

• 一对对应的括号只能涂其中一个括号
• 任意相邻的两个有颜色的括号颜色不能相同
• 涂的颜色只有两种，红色或蓝色

求合法涂色的方案数。

solution

区间dp

任意两个端点形成的区间[l,r]能有多少种涂色方案?

需要考虑这个区间[l,r]的两个端点是否是一对对应的括号。
如果是则考虑子问题[l+1, r-1]；如果不是则考虑子问题[l, ne[l]]和[ne[l]+1, r]，这里ne[l]代表l对应的右端点。

对于区间端点是成对的括号，这一对括号涂色的方案就只有4种，(0,1),(0,2),(1,0),(2,0)，其中0代表不涂色，1代表涂红色，2代表涂蓝色。

如果不是成对的括号涂色的方案9种情况都有可能，我们需要递归到子问题进行判断。

我们定义$f_{l,r,cl,cr}$为区间l到r，其中l涂色为cl，r涂色为cr的合法方案数。

对于$f_{l,r,cl,cr}$：

• l和r是一对对应括号
  • cl和cr是同一种颜色则$f_{l,r,cl,cr} = 0$
  • cl和cr非同一种颜色则$f_{l,r,cl,cr} = \sum \limits_{x,y\in \lbrace 1,2,3\rbrace ,cl和x不同色,y和cr不同色} f_{l,r,x,y}$，且满足cl和x不同色，cy和y不同色。
• l和r不是一对对应括号，则拆分出第一对括号的状态$f_{l,ne_l, cl, x}$和$f_{ne_l+1,r, y, cr}$，$f_{l,r,cl,cr} = \sum \limits_{x,y\in \lbrace 1,2,3\rbrace ,x和y不同色} f_{l,ne_l,cl,x}\times f_{ne_l+1, r, y, cr}$，为了满足相邻涂色的括号颜色不同，x和y除了都是0之外不能相等。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 705
#define MOD 1000000007
using namespace std;

ll f[N][N][3][3];

void sol() {
    vector<pair<int, int>> dir = {{0, 1}, {0, 2}, {1, 0}, {2, 0}};
    string s;
    cin >> s;
    int n = s.size();
    vector<int> ne(n, -1), st;
    for (int i = 0; i < n; i++) {
        if (s[i] == ')') {
            ne[st.back()] = i;
            st.pop_back();
        } else {
            st.push_back(i);
        }
    }
    // for (int i : ne) {
    //     cout << i << " ";
    // }
    // cout << endl;
    memset(f, -1, sizeof(f));
    function<ll(int, int, int, int)> dfs = [&](int l, int r, int cl, int cr) {
        if (f[l][r][cl][cr] != -1) {
            return f[l][r][cl][cr];
        }
        ll rt = 0;
        if (ne[l] == r) {
            if (cl == cr || cl && cr) {
                // cout << l << " " << r << " " << cl << " " << cr << " \n";
                return f[l][r][cl][cr] = 0;
            }
            if (l + 1 == r) {
                // cout << l << " " << r << " " << cl << " " << cr << " 1\n";
                return f[l][r][cl][cr] = 1;
            }
            for (int x = 0; x < 3; x++) {
                for (int y = 0; y < 3; y++) {
                    if (x == cl && x)
                        continue;
                    if (y == cr && y)
                        continue;
                    // cout << cl << " " << x << " " << y << " " << cr << endl;
                    rt += dfs(l + 1, r - 1, x, y);
                    rt %= MOD;
                }
            }
        } else {
            for (int x = 0; x < 3; x++) {
                for (int y = 0; y < 3; y++) {
                    if (x == y && x)
                        continue;
                    rt += dfs(l, ne[l], cl, x) * dfs(ne[l] + 1, r, y, cr) % MOD;
                    rt %= MOD;
                }
            }
        }
        // cout << l << " " << r << " " << cl << " " << cr << " " << rt << "\n";
        return f[l][r][cl][cr] = rt;
    };
    ll ans = 0;
    for (int x = 0; x < 3; x++) {
        for (int y = 0; y < 3; y++) {
            ans += dfs(0, n - 1, x, y);
            ans %= MOD;
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}