[text] F_bracket_sequence

Viewer

copydownloadembedprintName: F_bracket_sequence
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. // policy based datastructure
  5. // #include <ext/pb_ds/assoc_container.hpp>
  6. // using namespace __gnu_pbds;
  7. // typedef tree<int,null_type,less<int>,rb_tree_tag,
  8. // tree_order_statistics_node_update> indexed_set;
  9.  
  10. #define ll long long
  11. #define en '\n'
  12. #define ff first
  13. #define ss second
  14. #define pb push_back
  15. #define MP make_pair
  16. #define mod 1000000007
  17. // #define mod 998244353
  18. #define fast                      \
  19.     ios_base::sync_with_stdio(0); \
  20.     cin.tie(0);                   \
  21.     cout.tie(0);
  22. using namespace std;
  23.  
  24. typedef vector<ll> vi;
  25. typedef vector<vi> vvi;
  26. typedef priority_queue<ll> pqi;
  27. typedef priority_queue<ll, vi, greater<ll>> minpqi;
  28. typedef pair<ll, ll> pii;
  29.  
  30. #define all(x) x.begin(), x.end()
  31. #define present(c, key) (find(all(c), key) != c.end())
  32. #define tr(c, it) for (auto it : c)
  33. #define fr(i, s, e) for (ll i = s; i < e; i++)
  34. #define revfr(i, s, e) for (ll i = s - 1; i >= e; i--)
  35. #define getv(v, n)             \
  36.     for (ll i = 0; i < n; i++) \
  37.         cin >> v[i];
  38.  
  39. template <typename T>
  40. ostream &operator<<(ostream &os, vector<T> &v)
  41. {
  42.  
  43.     for (auto element : v)
  44.     {
  45.         os << element << ' ';
  46.     }
  47.     return os;
  48. }
  49. inline void add(ll &a, ll b)
  50. {
  51.     a += b;
  52.     if (a >= mod)
  53.         a -= mod;
  54. }
  55.  
  56. inline void sub(ll &a, ll b)
  57. {
  58.     a -= b;
  59.     if (a < 0)
  60.         a += mod;
  61. }
  62.  
  63. inline ll mul(ll a, ll b, ll p = mod)
  64. {
  65.     return (ll)((long long)a * b % p);
  66. }
  67.  
  68. inline ll power(ll a, long long b, ll p = mod)
  69. {
  70.     ll res = 1;
  71.     while (b > 0)
  72.     {
  73.         if (b & 1)
  74.         {
  75.             res = mul(res, a, p);
  76.         }
  77.         a = mul(a, a, p);
  78.         b >>= 1;
  79.     }
  80.     return res;
  81. }
  82. inline ll inv(ll a, ll p = mod)
  83. {
  84.     a %= p;
  85.     if (a < 0)
  86.         a += p;
  87.     ll b = p, u = 0, v = 1;
  88.     while (a)
  89.     {
  90.         ll t = b / a;
  91.         b -= t * a;
  92.         swap(a, b);
  93.         u -= t * v;
  94.         swap(u, v);
  95.     }
  96.     if (u < 0)
  97.         u += p;
  98.     return u;
  99. }
  100. // inline ll lsb(ll x)
  101. // {
  102. //     return x&(~(x-1));
  103. // }
  104. // ll modexp2(ll a, ll b, ll c, ll p) // calculate (a^(b^c))%prime
  105. // {
  106. //     // By Fermat's Little Theorem (a^(p-1))%p = 1 if p is prime
  107. //     ll x = power(b,c,p-1);  // so we first find remainder when b^c is divided by p-1
  108. //     return (power(a,x,p));  // then just do (a^remainder)%p
  109.  
  110. // }
  111. ll gcd(ll a, ll b)
  112. {
  113.     if (a == 0 or b == 0)
  114.         return a ^ b;
  115.     return gcd(b, a % b);
  116. }
  117. void fread()
  118. {
  119.     // #ifdef ONLINE_JUDGE
  120.     freopen("./input.txt", "r", stdin);
  121.     freopen("./output.txt", "w", stdout);
  122.     // #endif
  123. }
  124. ll n, len;
  125. string s;
  126. ll dp[210][210][210][2];
  127. ll rec(ll lvl, ll pos, ll sc, ll f)
  128. {
  129.     if (sc < 0)
  130.         return 0;
  131.     if (lvl == (2*n))
  132.     {
  133.         if (pos == len and sc == 0)
  134.             return 1;
  135.         return 0;
  136.     }
  137.     if (dp[lvl][pos][sc][f] != -1)
  138.         return dp[lvl][pos][sc][f];
  139.     ll ans = 0;
  140.     if (f)
  141.     {
  142.         ans = rec(lvl + 1, pos + 1, sc + (2 * (s[pos] == '(')) - 1, f ^ ((pos + 1) == len));
  143.     }
  144.     else
  145.     {
  146.         (ans += rec(lvl + 1, pos, sc + 1, 0)) %= mod;
  147.         (ans += rec(lvl + 1, pos, sc - 1, 0)) %= mod;
  148.         if (pos == 0)
  149.         {
  150.             (ans += rec(lvl, pos, sc, 1)) %= mod;
  151.         }
  152.     }
  153.     return dp[lvl][pos][sc][f] = ans;
  154. }
  155. void solve()
  156. {
  157.     cin>>n;
  158.     cin>>s;
  159.     len=s.size();
  160.     memset(dp,-1,sizeof(dp));
  161.     cout<<rec(0,0,0,0)<<en;
  162. }
  163. using namespace std;
  164.  
  165. int main()
  166. {
  167.     fast
  168.     // fread();
  169.     ll _t = 1;
  170.     // cin >> _t;
  171.     fr(i, 1, _t + 1)
  172.     {
  173.         // cout<<"Case #"<<i<<": ";
  174.         solve();
  175.     }
  176.     return 0;
  177. }

Editor

You can edit this paste and save as new:


File Description
  • F_bracket_sequence
  • Paste Code
  • 23 Dec-2022
  • 3.63 Kb
You can Share it: