- #include <iostream>
- #include <bits/stdc++.h>
- // policy based datastructure
- // #include <ext/pb_ds/assoc_container.hpp>
- // using namespace __gnu_pbds;
- // typedef tree<int,null_type,less<int>,rb_tree_tag,
- // tree_order_statistics_node_update> indexed_set;
- #define ll long long
- #define en '\n'
- #define ff first
- #define ss second
- #define pb push_back
- #define MP make_pair
- #define mod 1000000007
- // #define mod 998244353
- #define fast \
- ios_base::sync_with_stdio(0); \
- cin.tie(0); \
- cout.tie(0);
- using namespace std;
- typedef vector<ll> vi;
- typedef vector<vi> vvi;
- typedef priority_queue<ll> pqi;
- typedef priority_queue<ll, vi, greater<ll>> minpqi;
- typedef pair<ll, ll> pii;
- #define all(x) x.begin(), x.end()
- #define present(c, key) (find(all(c), key) != c.end())
- #define tr(c, it) for (auto it : c)
- #define fr(i, s, e) for (ll i = s; i < e; i++)
- #define revfr(i, s, e) for (ll i = s - 1; i >= e; i--)
- #define getv(v, n) \
- for (ll i = 0; i < n; i++) \
- cin >> v[i];
- template <typename T>
- ostream &operator<<(ostream &os, vector<T> &v)
- {
- for (auto element : v)
- {
- os << element << ' ';
- }
- return os;
- }
- inline void add(ll &a, ll b)
- {
- a += b;
- if (a >= mod)
- a -= mod;
- }
- inline void sub(ll &a, ll b)
- {
- a -= b;
- if (a < 0)
- a += mod;
- }
- inline ll mul(ll a, ll b, ll p = mod)
- {
- return (ll)((long long)a * b % p);
- }
- inline ll power(ll a, long long b, ll p = mod)
- {
- ll res = 1;
- while (b > 0)
- {
- if (b & 1)
- {
- res = mul(res, a, p);
- }
- a = mul(a, a, p);
- b >>= 1;
- }
- return res;
- }
- inline ll inv(ll a, ll p = mod)
- {
- a %= p;
- if (a < 0)
- a += p;
- ll b = p, u = 0, v = 1;
- while (a)
- {
- ll t = b / a;
- b -= t * a;
- swap(a, b);
- u -= t * v;
- swap(u, v);
- }
- if (u < 0)
- u += p;
- return u;
- }
- // inline ll lsb(ll x)
- // {
- // return x&(~(x-1));
- // }
- // ll modexp2(ll a, ll b, ll c, ll p) // calculate (a^(b^c))%prime
- // {
- // // By Fermat's Little Theorem (a^(p-1))%p = 1 if p is prime
- // ll x = power(b,c,p-1); // so we first find remainder when b^c is divided by p-1
- // return (power(a,x,p)); // then just do (a^remainder)%p
- // }
- ll gcd(ll a, ll b)
- {
- if (a == 0 or b == 0)
- return a ^ b;
- return gcd(b, a % b);
- }
- void fread()
- {
- // #ifdef ONLINE_JUDGE
- freopen("./input.txt", "r", stdin);
- freopen("./output.txt", "w", stdout);
- // #endif
- }
- ll n, len;
- string s;
- ll dp[210][210][210][2];
- ll rec(ll lvl, ll pos, ll sc, ll f)
- {
- if (sc < 0)
- return 0;
- if (lvl == (2*n))
- {
- if (pos == len and sc == 0)
- return 1;
- return 0;
- }
- if (dp[lvl][pos][sc][f] != -1)
- return dp[lvl][pos][sc][f];
- ll ans = 0;
- if (f)
- {
- ans = rec(lvl + 1, pos + 1, sc + (2 * (s[pos] == '(')) - 1, f ^ ((pos + 1) == len));
- }
- else
- {
- (ans += rec(lvl + 1, pos, sc + 1, 0)) %= mod;
- (ans += rec(lvl + 1, pos, sc - 1, 0)) %= mod;
- if (pos == 0)
- {
- (ans += rec(lvl, pos, sc, 1)) %= mod;
- }
- }
- return dp[lvl][pos][sc][f] = ans;
- }
- void solve()
- {
- cin>>n;
- cin>>s;
- len=s.size();
- memset(dp,-1,sizeof(dp));
- cout<<rec(0,0,0,0)<<en;
- }
- using namespace std;
- int main()
- {
- fast
- // fread();
- ll _t = 1;
- // cin >> _t;
- fr(i, 1, _t + 1)
- {
- // cout<<"Case #"<<i<<": ";
- solve();
- }
- return 0;
- }
[text] F_bracket_sequence
Viewer
*** This page was generated with the meta tag "noindex, nofollow". This happened because you selected this option before saving or the system detected it as spam. This means that this page will never get into the search engines and the search bot will not crawl it. There is nothing to worry about, you can still share it with anyone.
Editor
You can edit this paste and save as new: