fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define PB push_back
  5. #define FI first
  6. #define SE second
  7. #define MP make_pair
  8. #define ALL(DATAST) DATAST.begin(), DATAST.end()
  9. #define MOD 1000000007ll
  10. #define SIZE 100100ll
  11.  
  12. ll power(ll a, ll b)
  13. {
  14.     ll res = 1;
  15.     a = (a % MOD);
  16.     while (b)
  17.     {
  18.         if (b & 1)
  19.             res = (res * a) % MOD;
  20.         b >>= 1;
  21.         a = (a * a) % MOD;
  22.     }
  23.     return res;
  24. }
  25.  
  26. ll inverse(ll a)
  27. {
  28.     return power(a, MOD - 2);
  29. }
  30.  
  31. ll fact[SIZE];
  32. ll invfact[SIZE];
  33.  
  34. void precomp()
  35. {
  36.     fact[0] = 1;
  37.     invfact[0] = 1;
  38.     for (ll i = 1; i < SIZE; i++)
  39.     {
  40.         fact[i] = (fact[i - 1] * i) % MOD;
  41.         invfact[i] = (inverse(i) * invfact[i - 1]) % MOD;
  42.     }
  43. }
  44.  
  45. ll ncr(ll n, ll r)
  46. {
  47.     ll val = fact[n];
  48.     val = (val * invfact[n - r]) % MOD;
  49.     val = (val * invfact[r]) % MOD;
  50.     return val;
  51. }
  52.  
  53. ll catalan(ll n)
  54. {
  55.     ll val = ncr(2 * n, n);
  56.     val = (val * inverse(n + 1)) % MOD;
  57.     return val;
  58. }
  59.  
  60. map<pair<ll, ll>, ll>um;
  61.  
  62. ll recur(ll a, ll b)
  63. {
  64.     if (a == 0 && b == 0)
  65.         return 1;
  66.     if (a == 0)
  67.         return 0;
  68.     if (b == 0)
  69.     {
  70.         if (a % 2)
  71.             return 0;
  72.         else
  73.             return catalan(a / 2);
  74.     }
  75.     b = abs(b);
  76.     if (a < b)
  77.         return 0;
  78.     pair<ll, ll>P = MP(a, b);
  79.     if (um.find(P) != um.end())
  80.         return um[P];
  81.     um[P] = recur(a - 1, b + 1) + recur(a - 1, b - 1);
  82.     return um[P];
  83. }
  84.  
  85. int main()
  86. {
  87.     ios::sync_with_stdio(0);
  88.     cin.tie(0); cout.tie(0);
  89. #ifndef ONLINE_JUDGE
  90.     freopen("input.txt", "r", stdin);
  91.     freopen("output.txt", "w", stdout);
  92. #endif
  93.  
  94.  
  95.  
  96.     precomp();
  97.  
  98.  
  99.     ll m, n;
  100.  
  101.     cin >> n >> m;
  102.  
  103.     string x;
  104.  
  105.     cin >> x;
  106.  
  107.     ll req = 0;
  108.  
  109.     ll balance = 0;
  110.  
  111.     for (ll i = 0; i < m; i++)
  112.     {
  113.         if (x[i] == '(')
  114.             balance++;
  115.         else
  116.             balance--;
  117.         req = min(balance, req);
  118.     }
  119.     // i need minimum req brackets
  120.     // so that a+s+b the closing brackets of
  121.     // s are balanced
  122.     req = -req;
  123.     // cout<<"jfc  "<<req<<" "<<balance<<"  edc"<<endl;
  124.     ll ans = 0;
  125.     for (ll i = 0; i <= n - m; i++)
  126.     {
  127.         cout<<i<<": "<<endl;
  128.         for (ll j = req; j <= i; j++)
  129.         {
  130.             ll aa = recur(i, j);
  131.             cout<<i<<" of balance "<<j<<": "<<aa;
  132.             ll bb = recur(n - m - i, j + balance);
  133.             cout<<" :: & "<<n-m-i<<" of balance "<<j+balance<<": "<<bb<<endl;
  134.             ll curr = 0;
  135.             curr = (aa * bb) % MOD;
  136.             ans = (ans + curr) % MOD;
  137.         }
  138.         cout<<endl;
  139.     }
  140.  
  141.     cout << ans << endl;
  142.  
  143.  
  144.     return 0;
  145.  
  146.  
  147. }
Success #stdin #stdout 0.01s 5028KB
comments (?)
stdin
copy 
6 2
((
stdout
copy 
0: 
0 of balance 0: 1 :: & 4 of balance 2: 3

1: 
1 of balance 0: 0 :: & 3 of balance 2: 0
1 of balance 1: 1 :: & 3 of balance 3: 1

2: 
2 of balance 0: 1 :: & 2 of balance 2: 1
2 of balance 1: 0 :: & 2 of balance 3: 0
2 of balance 2: 1 :: & 2 of balance 4: 0

3: 
3 of balance 0: 0 :: & 1 of balance 2: 0
3 of balance 1: 2 :: & 1 of balance 3: 0
3 of balance 2: 0 :: & 1 of balance 4: 0
3 of balance 3: 1 :: & 1 of balance 5: 0

4: 
4 of balance 0: 2 :: & 0 of balance 2: 0
4 of balance 1: 0 :: & 0 of balance 3: 0
4 of balance 2: 3 :: & 0 of balance 4: 0
4 of balance 3: 0 :: & 0 of balance 5: 0
4 of balance 4: 1 :: & 0 of balance 6: 0

5
https://ideone.com/8s4J60
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!