Source code for submission s958

fq.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <utility>
  7. #include <string>
  8. #include <deque>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <stack>
  14. #include <vector>
  15. using namespace std;
  16.  
  17. //#define debug printf
  18. #define debug blackhole
  19. void blackhole(...) {}
  20.  
  21. #define MOD 1000000
  22.  
  23. char line[10000];
  24. int table[10000][10000];
  25.  
  26. void solve() {
  27. if (strlen(line)%2 == 1) {
  28. printf("0\n");
  29. return;
  30. }
  31.  
  32. for (int i = 0; i < 10000; i++) {
  33. for (int j = 0; j < 10000; j++) {
  34. table[i][j] = 0;
  35. }
  36. }
  37.  
  38. table[0][0] = 1;
  39. int len = strlen(line);
  40. for (int j = 1; j <= len/2; j++) {
  41. if (line[j - 1] == ')') {
  42. table[0][j] = 0;
  43. } else {
  44. table[0][j] = table[0][j - 1];
  45. }
  46. }
  47. for (int i = 1; i <= len/2; i++) {
  48. if (line[i * 2 - 1] == ')' || line[i * 2 - 1] == '.') {
  49. table[i][i] = table[i-1][i];
  50. } else {
  51. table[i][i] = 0;
  52. }
  53.  
  54. for (int j = i + 1; j <= len/2; j++) {
  55. table[i][j] = 0;
  56. int index = i + j - 1;
  57. char c = line[index];
  58.  
  59. if (c == ')' || c == '.') {
  60. table[i][j] = (table[i][j] + table[i-1][j]) % MOD;
  61. }
  62. if (c == '(' || c == '.') {
  63. table[i][j] = (table[i][j] + table[i][j-1]) % MOD;
  64. }
  65. }
  66. }
  67.  
  68. for (int i=0;i<=len/2;i++) {
  69. for (int j=0;j<=len/2;j++) {
  70. debug("%d\t", table[i][j]);
  71. }
  72. debug("\n");
  73. }
  74. debug("\n");
  75.  
  76. printf("%d\n", table[len/2][len/2]);
  77. }
  78.  
  79. int main() {
  80. while (true) {
  81. if (scanf("%s", line) != 1) break;
  82. debug("line: %s\n", line);
  83. solve();
  84. }
  85. return 0;
  86. }
  87.