fork download
  1. // author : Nguyễn Trọng Nguyễn - ITK22 NBK
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define ii pair <int, int>
  7. #define fi first
  8. #define sc second
  9.  
  10. const int maxn = 3000;
  11. const int inf = (int)1e9;
  12. const int mod = (int)1e9 + 7;
  13.  
  14. int t, n, k;
  15. char a[maxn + 5];
  16. ll dp[maxn + 5][maxn / 2 + 5];
  17.  
  18. char s[6] = {'(', ')', '[', ']', '{', '}'};
  19. ll rnk = 1;
  20. stack <char> st;
  21.  
  22. void add (ll &a, ll b) {
  23. a += b;
  24. if (a >= mod) a -= mod;
  25. }
  26.  
  27. void init () {
  28. cin >> t >> n >> k;
  29. for (int i = 0; i < n; i++)
  30. cin >> a[i];
  31. }
  32.  
  33. ll calc (int id = 0, int len = 0) {
  34. if (len < 0 or len > k) return 0;
  35. if (id == n) return len == 0;
  36.  
  37. if (dp[id][len] != -1) return dp[id][len];
  38.  
  39. ll res = 0;
  40. int mx = t == 1 ? 2 : 6;
  41. for (int i = 0; i < mx; i++) {
  42. if (i & 1) {
  43. if (len == 0 or st.top() != s[i - 1]) continue;
  44. st.pop();
  45. add(res, calc(id + 1, len - 1));
  46. st.push(s[i - 1]);
  47. }
  48. else {
  49. st.push(s[i]);
  50. add(res, calc(id + 1, len + 1));
  51. st.pop();
  52. }
  53. }
  54.  
  55. return dp[id][len] = res;
  56. }
  57.  
  58. void getrank (int id = 0, int len = 0) {
  59. if (id == n or len < 0 or len > k) return ;
  60.  
  61. int mx = t == 1 ? 2 : 6;
  62. for (int i = 0; i < mx; i++) {
  63. if (i & 1) {
  64. if (len == 0 or st.top() != s[i - 1]) continue;
  65. st.pop();
  66. if (a[id] != s[i]) add(rnk, calc(id + 1, len - 1));
  67. else {
  68. getrank(id + 1, len - 1);
  69. return ;
  70. }
  71. st.push(s[i - 1]);
  72. }
  73. else {
  74. st.push(s[i]);
  75. if (a[id] != s[i]) add(rnk, calc(id + 1, len + 1));
  76. else {
  77. getrank(id + 1, len + 1);
  78. return ;
  79. }
  80. st.pop();
  81. }
  82. }
  83. }
  84.  
  85. void process () {
  86. memset(dp, -1, sizeof dp);
  87. ll total = calc();
  88. getrank();
  89. cout << rnk;
  90. }
  91.  
  92. signed main () {
  93. cin.tie(0)->sync_with_stdio(false);
  94.  
  95. #ifndef ONLINE_JUDGE
  96. freopen("test.inp","r",stdin);
  97. freopen("test.out","w",stdout);
  98. #endif
  99.  
  100. init();
  101. process();
  102.  
  103. return 0;
  104. }
Success #stdin #stdout 0.01s 38896KB
stdin
Standard input is empty
stdout
1