fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. class BracketSequenceDiv1 {
  7. public:
  8. int n;
  9. string s;
  10. typedef long long LL;
  11. LL memo[41][41][41][4];
  12.  
  13. LL f(int p, int Lr, int Ls, int last)
  14. {
  15. if (p == n)
  16. return Lr == 0 && Ls == 0 && last != 3;
  17.  
  18. LL& res = memo[p][Lr][Ls][last];
  19. if (res != -1LL)
  20. return res;
  21. res = 0;
  22. if (s[p] == '(')
  23. {
  24. res = f(p+1, Lr+1, Ls, 0)+f(p+1, Lr, Ls, last);
  25. }
  26. else if (s[p] == '[')
  27. {
  28. res = f(p+1, Lr, Ls+1, 1)+f(p+1, Lr, Ls, last);
  29. }
  30. else if (s[p] == ')')
  31. {
  32. if (Lr == 0 && Ls == 0)
  33. res = f(p+1, Lr, Ls, last);
  34. else if (Lr > 0 && Ls == 0)
  35. res = f(p+1, Lr, Ls, last)+f(p+1, Lr-1, Ls, Lr-1?0:2);
  36. else if (Lr == 0 && Ls > 0)
  37. res = f(p+1, Lr, Ls, last);
  38. else // Lr > 0 && Ls > 0
  39. {
  40. res = f(p+1, Lr, Ls, last);
  41. if (last != 1)
  42. res += f(p+1, Lr-1, Ls, Lr-1?0:1);
  43. }
  44. }
  45. else // s[p] == ']'
  46. {
  47. if (Lr == 0 && Ls == 0)
  48. res = f(p+1, Lr, Ls, last);
  49. else if (Lr > 0 && Ls == 0)
  50. res = f(p+1, Lr, Ls, last);
  51. else if (Lr == 0 && Ls > 0)
  52. res = f(p+1, Lr, Ls, last)+f(p+1, Lr, Ls-1, Ls-1?1:2);
  53. else
  54. {
  55. res = f(p+1, Lr, Ls, last);
  56. if (last != 0)
  57. res += f(p+1, Lr, Ls-1, Ls-1?1:0);
  58. }
  59. }
  60. return res;
  61. }
  62.  
  63. long long count(string s_)
  64. {
  65. s = s_;
  66. n = s.size();
  67. memset(memo, -1, sizeof(memo));
  68.  
  69. return f(0, 0, 0, 3);
  70. }
  71. };
  72.  
  73.  
  74. <%:testing-code%>
  75. //Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
prog.cpp:74:1: error: expected unqualified-id before '<%' token
 <%:testing-code%>
 ^
stdout
Standard output is empty