fork download
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5.  
  6. template <typename T>
  7. inline bool maxi(T &x, const T &val)
  8. {
  9. if (x < val)
  10. return x = val, true;
  11. return false;
  12. }
  13.  
  14. template <typename T>
  15. inline bool mini(T &x, const T &val)
  16. {
  17. if (x > val)
  18. return x = val, true;
  19. return false;
  20. }
  21.  
  22. const int maxn = 3010, maxk = maxn / 2, mod = 1e9 + 7;
  23. int n, k;
  24. string s;
  25. int dp[maxn][2][maxk];
  26.  
  27. inline void add(int &x, const int &val)
  28. {
  29. if ((x += val) >= mod) x -= mod;
  30. }
  31.  
  32. int cal(int x, int type, int cur)
  33. {
  34. if (x == n)
  35. {
  36. return cur == 0;
  37. }
  38. int &d = dp[x][type][cur];
  39. if (d != -1)
  40. return d;
  41. d = 0;
  42. if (cur < k)
  43. {
  44. add(d, 3ll * cal(x + 1, 0, cur + 1) % mod);
  45. }
  46. if (cur > 0)
  47. {
  48. add(d, cal(x + 1, 1, cur - 1));
  49. }
  50. return d;
  51. }
  52.  
  53. int calsub1(int x, int type, int cur)
  54. {
  55. if (x == n)
  56. {
  57. return cur == 0;
  58. }
  59. int &d = dp[x][type][cur];
  60. if (d != -1)
  61. return d;
  62. d = 0;
  63. if (cur < k)
  64. {
  65. add(d, calsub1(x + 1, 0, cur + 1) % mod);
  66. }
  67. if (cur > 0)
  68. {
  69. add(d, cal(x + 1, 1, cur - 1));
  70. }
  71. return d;
  72. }
  73.  
  74. void solvesub1()
  75. {
  76. memset(dp, -1, sizeof dp);
  77. int res = 1;
  78. int cur = 0;
  79. vector<char> dak;
  80. for (int i = 0; i < n; i++)
  81. {
  82. if (cur < k) {
  83. if ('(' < s[i])
  84. {
  85. add(res, calsub1(i + 1, 0, cur + 1));
  86. }
  87. }
  88. if (s[i] == '(')
  89. {
  90. dak.push_back(s[i]);
  91. cur++;
  92. }
  93. else
  94. {
  95. dak.pop_back();
  96. cur--;
  97. }
  98. }
  99. cout << res << '\n';
  100. }
  101.  
  102. void solve()
  103. {
  104. int T;
  105. cin >> T;
  106. cin >> n >> k;
  107. cin >> s;
  108. if (T == 1) {
  109. solvesub1();
  110. return;
  111. }
  112. memset(dp, -1, sizeof dp);
  113. int res = 1;
  114. int cur = 0;
  115. vector<char> dak;
  116. for (int i = 0; i < n; i++)
  117. {
  118. if (cur < k) {
  119. if ('(' < s[i])
  120. {
  121. add(res, cal(i + 1, 0, cur + 1));
  122. }
  123. if ('[' < s[i])
  124. {
  125. add(res, cal(i + 1, 0, cur + 1));
  126. }
  127. if ('{' < s[i])
  128. {
  129. add(res, cal(i + 1, 0, cur + 1));
  130. }
  131. }
  132. if (cur > 0) {
  133. char c = dak.back();
  134. if ((c == '(' && ')' < s[i])
  135. || (c == '[' && ']' < s[i])
  136. || (c == '{' && '}' < s[i])) {
  137. add(res, cal(i + 1, 1, cur - 1));
  138. }
  139. }
  140. if (s[i] == '(' || s[i] == '[' || s[i] == '{')
  141. {
  142. dak.push_back(s[i]);
  143. cur++;
  144. }
  145. else
  146. {
  147. dak.pop_back();
  148. cur--;
  149. }
  150. }
  151. cout << res << '\n';
  152. }
  153.  
  154. signed main()
  155. {
  156. #ifndef ONLINE_JUDGE
  157. freopen("test.inp","r",stdin);
  158. freopen("test.out","w",stdout);
  159. #endif
  160. solve();
  161. }
  162.  
Success #stdin #stdout 0.02s 74368KB
stdin
Standard input is empty
stdout
1