Source code for submission s537

fq.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25.  
  26. const int INF = 1<<29;
  27. typedef long long ll;
  28. ///////////////////////////////////////////////////////////////////////////
  29.  
  30. const int MAX = 1024, MOD = 1000000;
  31. char in[MAX];
  32. int N;
  33.  
  34. int dp[MAX][MAX];
  35.  
  36. int go(int n, int s)
  37. {
  38. int & res = dp[n][s];
  39. if (res != -1) return res;
  40.  
  41. res = 0;
  42. if (n == N)
  43. {
  44. return res = s==0;
  45. }
  46.  
  47. if (in[n] == '.')
  48. {
  49. if (s < N/2)
  50. {
  51. res += go(n+1, s+1);
  52. }
  53. if (s > 0)
  54. {
  55. res += go(n+1, s-1);
  56. }
  57. }
  58. else if (in[n] == '(')
  59. {
  60. if (s < N/2)
  61. {
  62. res += go(n+1, s+1);
  63. }
  64. }
  65. else
  66. {
  67. if (s > 0)
  68. {
  69. res += go(n+1, s-1);
  70. }
  71. }
  72.  
  73. res %= MOD;
  74. return res;
  75. }
  76.  
  77. int main()
  78. {
  79. while (gets(in))
  80. {
  81. N = strlen(in);
  82. REP(i, N+1) REP(j, N+1) dp[i][j] = -1;
  83. printf("%d\n", go(0, 0));
  84. }
  85.  
  86. return 0;
  87. }