Advertisement
Guest User

Untitled

a guest
Mar 18th, 2018
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long C[777][777];
  6.  
  7. int r, c;
  8. long long total;
  9. long long best = (long long) 1e18, best_z = -1;
  10.  
  11. void dfs(long long x, long long y, int v1, int v2) {
  12. long long diff = abs(x - y);
  13. if (best <= 1 || diff - C[v1][r] * C[v2][r] >= best) {
  14. return;
  15. }
  16. if (v1 == r - 1 && v2 == r - 1) {
  17. long long diff = abs(x - y);
  18. if (diff < best) {
  19. best = diff;
  20. best_z = x;
  21. }
  22. return;
  23. }
  24. if (v1 >= r) {
  25. long long cur1 = C[v1][r] - C[v1 - 1][r];
  26. long long sum2 = C[v2][r];
  27. dfs(x, y + cur1 * sum2, v1 - 1, v2);
  28. }
  29. if (v2 >= r) {
  30. long long sum1 = C[v1][r];
  31. long long cur2 = C[v2][r] - C[v2 - 1][r];
  32. dfs(x + sum1 * cur2, y, v1, v2 - 1);
  33. }
  34. }
  35.  
  36. char s[12345];
  37. int cntA[12345], cntB[12345];
  38. map<long long, long long> mp;
  39.  
  40. long long solve(long long x, long long y, int v1, int v2) {
  41. long long state = x * 10000 + v1 * 100 + v2;
  42. if (mp.find(state) != mp.end()) {
  43. return mp[state];
  44. }
  45. long long &res = mp[state];
  46. long long diff = abs(x - y);
  47. if (diff - C[v1][r] * C[v2][r] > best) {
  48. return res = 0;
  49. }
  50. if (v1 < r || v2 < r) {
  51. if (v1 >= cntA[v1 + v2] && v2 >= cntB[v1 + v2]) {
  52. int sum = v1 + v2;
  53. v1 -= cntA[sum];
  54. v2 -= cntB[sum];
  55. return res = C[v1 + v2][v1];
  56. }
  57. return res = 0;
  58. }
  59. res = 0;
  60. char c = s[v1 + v2 - 1];
  61. if (c != 'B') {
  62. long long cur1 = C[v1][r] - C[v1 - 1][r];
  63. long long sum2 = C[v2][r];
  64. res += solve(x, y + cur1 * sum2, v1 - 1, v2);
  65. }
  66. if (c != 'A') {
  67. long long sum1 = C[v1][r];
  68. long long cur2 = C[v2][r] - C[v2 - 1][r];
  69. res += solve(x + sum1 * cur2, y, v1, v2 - 1);
  70. }
  71. return res;
  72. }
  73.  
  74. int main() {
  75. scanf("%d %d", &r, &c);
  76. for (int i = 0; i <= 2 * (r + c); i++) {
  77. for (int j = 0; j <= 2 * (r + c); j++) {
  78. if (j == 0) C[i][j] = 1; else
  79. if (i == 0) C[i][j] = 0;
  80. else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]);
  81. }
  82. }
  83. total = C[r + c][r] * C[r + c][r];
  84. {
  85. long long x = 0, y = 0;
  86. int v1 = r + c, v2 = r + c;
  87. while (v1 >= r && v2 >= r) {
  88. if (x > y) {
  89. long long cur1 = C[v1][r] - C[v1 - 1][r];
  90. long long sum2 = C[v2][r];
  91. y += cur1 * sum2;
  92. v1--;
  93. } else {
  94. long long sum1 = C[v1][r];
  95. long long cur2 = C[v2][r] - C[v2 - 1][r];
  96. x += sum1 * cur2;
  97. v2--;
  98. }
  99. }
  100. best = abs(x - y);
  101. }
  102. dfs(0, 0, r + c, r + c);
  103. scanf("%s", s);
  104. cntA[0] = cntB[0] = 0;
  105. for (int i = 0; i < 2 * (r + c); i++) {
  106. cntA[i + 1] = cntA[i] + (s[i] == 'A');
  107. cntB[i + 1] = cntB[i] + (s[i] == 'B');
  108. }
  109. long long ans = solve(0, 0, r + c, r + c);
  110. cout << ans << endl;
  111. return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement