# Dãy ngoặc

Nguồn: tham khảo bài trên [VNOJ](https://oj.vnoi.info/problem/adbrack?fbclid=IwAR2c8YUISC9R2PX1YTxmVm2g15__FJoYOVjlgIqiXUaHlgr8h2vlOB8X8KI)

Rating: 2000.

## Đề bài

Dãy ngoặc đúng được định nghĩa như sau:
- Biểu thức rỗng là biểu thức ngoặc đúng có bậc bằng $0$.
- Nếu $A$ là biểu thức ngoặc đúng có bậc bằng $k$ thì ($A$), [$A$], {$A$} cũng là biểu thức ngoặc đúng có bậc $k + 1$.
- Nếu $A$ và $B$ tương ứng là hai biểu thức ngoặc đúng có bậc là $k_A, k_B$ thì $AB$ cũng là một biểu thức ngoặc đúng có bậc bằng $max(k_A, k_B)$.

Ví dụ "()[()]" là một biểu thức ngoặc đúng có bậc bằng $2$.

Với hai số $n$, $k$ người ta tiến hành tạo ra tất cả các biểu thức ngoặc đúng có độ dài đúng bằng $n$ và có bậc không quá $k$. Sắp xếp các biểu thức ngoặc này theo thứ tự từ điển, chú ý: '(' $\le$ ')' $\le$ '[' $\le$ ']' $\le$ '{' $\le$ '}'.

#### Yêu cầu:
Cho $n$, $k$ và $A$, $B$ là hai biểu thức ngoặc đúng độ dài $n$ và có bậc không quá $k$. Hãy đếm xem có bao nhiêu biểu thức ngoặc đúng độ dài $n$ và có bậc không quá $k$ nằm giữa $A$ và $B$.

## Input:

- Dòng đầu chứa hai số nguyên $n, k$ ($1 \le 2k \le n \le 100$, $n$ chẵn).
- Dòng thứ hai chứa xâu $A$.
- Dòng thứ hai chứa xâu $B$.

## Output

- Một dòng duy nhất chứa số nguyên là số biểu thức ngoặc đúng độ dài $n$ và có bậc không quá $k$ nằm giữa $A$ và $B$.

## Sample


## Giới hạn

- Subtask 1: $10\%$ $n, k \le 10$.
- Subtask 2: $20\%$ $n \le 20, k \le 5$.
- Subtask 3: $30\%$ $n \le 100, k \le 5$.
- Subtask 4: $40\%$ Không có điều kiện gì thêm.

## Lời giải:

<details>
<summary>Lời giải</summary>

- Tư tưởng: ta đếm số lượng xâu nhỏ hơn A(a1), số lượng xâu nhỏ hơn B(b1). Đáp án sẽ là b1-a1-1.
Giả sử ta cần đếm số xâu nhỏ hơn S(ans)
Duy trì 1 biến i để duyệt xâu S, thử thay các ký tự nhỏ hơn S[i] vào vị trí i (gọi là c) và đếm có bao nhiêu xâu có dạng s[1..i-1] + c + z.
Lúc này, ans được cộng thêm số lượng xâu z thỏa mãn (z có độ dài n-i, sao cho thỏa mãn 1 dãy ngoặc đúng và có bậc nhỏ hơn k).
- Thuật toán:
Gọi d[i][j] là số lượng xâu có độ dài n-i+1 và nó kết hợp với j dấu mở ngoặc trước đó để tạo thành 1 dãy ngoặc đúng.
Ta có cách tính d[i][j] như sau:
• d[i][j] = d[i+1][j-1] nếu j=k
• d[i][j] = d[i+1][j+1]*3 nếu j=0
• d[i][j] = d[i][j+1]*3 + d[i][j-1] trong các trường hợp còn lại
+ Duyệt lần lượt các S[i], và xét 6 trường hợp là 6 ký tự. Ở mỗi
trường hợp. Ta thử thay các ký tự nhỏ hơn vào vị trí I thay cho S[i]. Giả sử ta có t = số dấu mở ngoặc hiện tại.
• Thêm 1 dấu mở : ans += d[i+1][t+1].
• Thêm 1 dấu đóng: Duy trì 1 stack để kiểm tra dấu mở ngoặc gần nhất và xem xét có đóng được hay không. Nếu được ta có ans+= d[i+1][t-1].
- Lưu ý: vì đáp án có thể rất lớn nên ta phải xử lý số lớn.
- Độ phức tạp O(n*k*z). Ở đây z là độ dài đáp án.

</details>

<details>
<summary>Code </summary>

#include <bits/stdc++.h>

using namespace std;
#define ll long long

const ll N = 1000;
ll n, k, i, j, t;
string d[N][N];
string s1, s2;
stack<ll> t1;

string cong(string a, string b) {
    string t; char tam;
    long long i, nho, x, y, c;
    while (a.size() > b.size()) b = '0' + b;
    while (b.size() > a.size()) a = '0' + a;
    nho = 0; c = 0; t = "";
    
    for (i = a.length() - 1; i >= 0; i--) {
        x = (int)a[i] - 48;
        y = (int)b[i] - 48;
        c = (x + y + nho) % 10;
        nho = (x + y + nho) / 10;
        tam = (char)c + 48;
        t = tam + t;
    }
    if (nho > 0) t = '1' + t;
    return t;
}

string tru(string a, string b) {

    string t = ""; char tam;
    long long i, nho, x, y, c;
    while(a.size() > b.size()) b = '0' + b;
    while(b.size() > a.size()) a = '0' + a;
    nho = 0; c = 0; t = "";
    
    for (i = a.length() - 1; i >= 0; i--) {
        x = (int)a[i] - 48;
        y = (int)b[i] - 48;
        c = x - y - nho;
        if (c >= 0) nho = 0;
        else {
            nho = 1;
            c = c + 10;
        }
        tam = (char)c + 48;
        t = tam + t;
    }
    while (t[0] == '0') t.erase(0, 1);
    if (t == "") return "0";
    return t;
}

string nhan(string a, long long so) {
    long long nho = 0, i;
    string t = "";
    for (i = a.length() - 1; i >= 0; i--) {
        nho = nho + (int)(a[i] - 48) * so;
        t = (char)(nho % 10 + 48) + t;
        nho /= 10;
    }
    while (nho > 0) {
        t = char(nho % 10 + 48) + t;
        nho /= 10;
    }
    return t;
}

string sol(ll i, ll t) {
    string p = d[i][t];
    ll o = (n - i + 1 - t) / 2;
    for(ll i = 1; i <= o; i++) 
        p = nhan(p, 3);
    return p;
}

string C(string s) {
    string ans = "0";
    while (!t1.empty()) 
        t1.pop();
    for (ll i = 1; i <= n; i++) {
        char c;
        c = s[i - 1];
        if (c == '(') {
            t++;
            t1.push(1);
            continue;
        }
        
        if (c == ')') {
          ans = cong(ans, sol(i + 1, t + 1));
          t--;
          t1.pop();
          continue;
        }
        
        if (c == '[') {
          ans = cong(ans, sol(i + 1, t + 1));
          if (!t1.empty()) 
              if (t1.top() == 1) ans = cong(ans, sol(i + 1, t - 1));
          t++;
          t1.push(2);
          continue;
        }
        
        if (c == ']') {
          ans = cong(ans, sol(i + 1, t + 1));
          if (!t1.empty()) 
              if (t1.top() == 1) ans = cong(ans, sol(i + 1, t - 1));
          ans = cong(ans, sol(i + 1, t + 1));
          t--;
          t1.pop();
          continue;
        }
        
        if (c == '{') {
          ans = cong(ans, sol(i + 1, t + 1));
          if (!t1.empty())
              if (t1.top() == 1) ans = cong(ans, sol(i + 1, t - 1));
          ans = cong(ans, sol(i + 1, t + 1));
          if (!t1.empty())
              if (t1.top() == 2) ans = cong(ans, sol(i + 1, t - 1));
          t++;
          t1.push(3);
          continue;
        }
        
        if (c == '}') {
            ans = cong(ans, sol(i + 1, t + 1));
            if (!t1.empty())
                if (t1.top() == 1) ans = cong(ans, sol(i + 1, t - 1));
            ans = cong(ans, sol(i + 1, t + 1));
            if (!t1.empty())
                if (t1.top() == 2) ans = cong(ans, sol(i + 1, t - 1));
            ans = cong(ans, sol(i + 1, t + 1));
            t--;
            t1.pop();
            continue;
        }
    }
    return cong(ans,"1");
}

int main() {
    cin >> n >> k;
    cin >> s1 >> s2;
    
    d[n + 1][0] = "1";
    for (i = n; i >= 1; i--)
    for (j = 0; j <= k; j++) {
        if (j == k) d[i][j] = d[i + 1][j - 1];
        else
            if (j == 0) d[i][j] = d[i + 1][j + 1]; 
            else d[i][j] = cong(d[i + 1][j - 1], d[i + 1][j + 1]);
    }
    
    cout << tru(tru(C(s2), C(s1)), "1");
    
    return 0;
}

</details>