welleyth

5205. Скобки (Brackets)

Nov 23rd, 2020
442
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define pb push_back
  6. #define mp make_pair
  7. #define FOR(i,a,b) for(int i = (a) ; i < (b) ; i++)
  8. #define ALL(A) A.begin(),A.end()
  9.  
  10. typedef vector<int> VI;
  11. typedef vector<VI> VVI;
  12.  
  13. const int INF = (int)1e9;
  14. const int MOD = (int)301907;
  15.  
  16. void solve_case()
  17. {
  18.     string s;
  19.     cin >> s;
  20.  
  21.     int n = s.size();
  22.  
  23.     vector<int> a(n+3,0);  /// Creating vector for odd positions
  24.     vector<int> b(n+3,0);  /// Creating vector for even positions
  25.  
  26.     a[1] = 1;
  27.  
  28.     if(n&1)  /// if n % 2 != 0, then we cannot even make 1 case to answer, so cout << 0
  29.     {
  30.         cout << "0";
  31.         return;
  32.     }
  33.  
  34.     for(int i = 1 ; i <= n ; i++)   /// Here do DP for i as position in string and j as amount of openned brackets, a[j] or b[j]
  35.                                     /// will be number of ways to go to this position with j openned brackets.
  36.     {
  37.         for(int j=2;j<=n;j+=2)
  38.         {
  39.             if(s[i - 1] == '(')
  40.                 b[j] = a[j-1] % MOD;
  41.             else if(s[i - 1] == ')')
  42.                 b[j] = a[j+1] % MOD;
  43.             else
  44.                 b[j] = (a[j-1] + a[j+1]) % MOD;
  45.         }
  46.  
  47.         i++;
  48.  
  49.         for(int j=1;j<=n;j+=2)
  50.         {
  51.             if(s[i - 1] == '(')
  52.                 a[j] = b[j-1] % MOD;
  53.             else if(s[i - 1] == ')')
  54.                 a[j] = b[j+1] % MOD;
  55.             else
  56.                 a[j] = (b[j-1] + b[j+1]) % MOD;
  57.         }
  58.     }
  59.  
  60.     cout << (a[1] + b[1]) % MOD;    /// Actually i didn`t want to think hard, so I cout sum of a[1] and b[1], but one of this parts
  61.                                     /// will be zero
  62.  
  63.     return;
  64. }
  65.  
  66. signed main()
  67. {
  68.     ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  69.  
  70. //    freopen("boxes.in","r",stdin);
  71. //    freopen("boxes.out","w",stdout);
  72.  
  73.     int t = 1;
  74. //    cin >> t;
  75.  
  76.     while(t--)
  77.     {
  78.         solve_case();
  79.     }
  80.  
  81.     return 0;
  82. }
RAW Paste Data