Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- #define pb push_back
- #define mp make_pair
- #define FOR(i,a,b) for(int i = (a) ; i < (b) ; i++)
- #define ALL(A) A.begin(),A.end()
- typedef vector<int> VI;
- typedef vector<VI> VVI;
- const int INF = (int)1e9;
- const int MOD = (int)301907;
- void solve_case()
- {
- string s;
- cin >> s;
- int n = s.size();
- vector<int> a(n+3,0); /// Creating vector for odd positions
- vector<int> b(n+3,0); /// Creating vector for even positions
- a[1] = 1;
- if(n&1) /// if n % 2 != 0, then we cannot even make 1 case to answer, so cout << 0
- {
- cout << "0";
- return;
- }
- 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]
- /// will be number of ways to go to this position with j openned brackets.
- {
- for(int j=2;j<=n;j+=2)
- {
- if(s[i - 1] == '(')
- b[j] = a[j-1] % MOD;
- else if(s[i - 1] == ')')
- b[j] = a[j+1] % MOD;
- else
- b[j] = (a[j-1] + a[j+1]) % MOD;
- }
- i++;
- for(int j=1;j<=n;j+=2)
- {
- if(s[i - 1] == '(')
- a[j] = b[j-1] % MOD;
- else if(s[i - 1] == ')')
- a[j] = b[j+1] % MOD;
- else
- a[j] = (b[j-1] + b[j+1]) % MOD;
- }
- }
- 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
- /// will be zero
- return;
- }
- signed main()
- {
- ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
- // freopen("boxes.in","r",stdin);
- // freopen("boxes.out","w",stdout);
- int t = 1;
- // cin >> t;
- while(t--)
- {
- solve_case();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement