﻿

# 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