fork download 
  1. // author : Nguyễn Trọng Nguyễn - ITK22 NBK
  2. #include <bits/stdc++.h>
  3.  
  4. #define int long long
  5. #define ii pair <int, int>
  6. #define fi first
  7. #define sc second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 200;
  12. const int MOD = 1e9 + 7;
  13.  
  14. int n, k;
  15. string st;
  16. int ans = 1;
  17. char s[6] = {'(', ')', '[', ']', '{', '}'};
  18. map <vector <char>, int> dp[maxn + 5];
  19.  
  20. inline int add(int a, int b) {
  21.     a += b;
  22.     if (a >= MOD) a -= MOD;
  23.     return a;
  24. }
  25.  
  26. int cal (vector <char> stack, int id = 0, int len = 0) {
  27.     if (len > k) return 0;
  28.     if (id == n) {
  29.         return (len == 0);
  30.     }
  31.  
  32.     if (dp[id].find(stack) != dp[id].end()) return dp[id][stack];
  33.  
  34.     int cnt = 0;
  35.     for (int i = 0; i < 6; i++) {
  36.         vector <char> newstack = stack;
  37.         int newlen = len;
  38.  
  39.         if (i & 1) { // đóng ngoặc
  40.             if (!newlen or newstack.back() != s[i - 1]) continue;
  41.             newstack.pop_back();
  42.             newlen--;
  43.             cnt = add(cnt, cal(newstack, id + 1, newlen));
  44.         }
  45.         else { // mở ngoặc
  46.             newstack.push_back(s[i]);
  47.             newlen++;
  48.             cnt = add(cnt, cal(newstack, id + 1, newlen));
  49.         }
  50.     }
  51.  
  52.     return dp[id][stack] = cnt;
  53. }
  54.  
  55. void get (vector <char> stack, int id = 0, int len = 0) {
  56.     if (id == n) return ;
  57.  
  58.     for (int i = 0; i < 6; i++) {
  59.         vector <char> newstack = stack;
  60.         int newlen = len;
  61.  
  62.         if (i & 1) { // đóng ngoặc
  63.             if (!newlen or newstack.back() != s[i - 1]) continue;
  64.             newstack.pop_back();
  65.             newlen--;
  66.             if (s[i] != st[id]) ans = add(ans, cal(newstack, id + 1, newlen));
  67.             else {
  68.                 get(newstack, id + 1, newlen);
  69.                 break;
  70.             }
  71.         }
  72.         else { // mở ngoặc
  73.             newstack.push_back(s[i]);
  74.             newlen++;
  75.             if (s[i] != st[id]) ans = add(ans, cal(newstack, id + 1, newlen));
  76.             else {
  77.                 get(newstack, id + 1, newlen);
  78.                 break;
  79.             }
  80.         }
  81.     }
  82. }
  83.  
  84. signed main (void) {
  85.     cin.tie(0)->sync_with_stdio(false);
  86.  
  87.     #ifndef ONLINE_JUDGE
  88.     freopen("test.inp","r",stdin);
  89.     freopen("test.out","w",stdout);
  90.     #endif
  91.  
  92.     int tc; cin >> tc; // không thấy dùng tc, giữ lại cho đủ input
  93.     cin >> n >> k >> st;
  94.  
  95.     vector <char> stack;
  96.     cal(stack);
  97.     stack.clear();
  98.     get(stack);
  99.     cout << ans % MOD;
  100.  
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
1
https://ideone.com/vXKLvh
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!