fork download
copy 
  1. #include<bits/stdc++.h>
  2. typedef long int ll;
  3. using namespace std;
  4.  
  5. ll mod = 1e9 + 7;
  6.  
  7. ll helper(ll val, ll j, ll finale, ll open, vector<ll> & arr, ll dp[][400])
  8.     {
  9.     if(open < 0)
  10.         return 0;
  11.     if(val > finale)
  12.         {
  13.         if(open == 0)
  14.             return 1ll;
  15.         else
  16.             return 0ll;
  17.         }
  18.     //else
  19.     if(dp[val][open] != -1)
  20.         return dp[val][open];
  21.     //else
  22.     if(arr[j] == val)
  23.         return dp[val][open] = helper(val + 1, j + 1, finale, open + 1, arr, dp)%mod;
  24.     else 
  25.         {
  26.         ll one,two;
  27.         one = two = 0;
  28.         if(open > 0)
  29.             one = helper(val + 1, j, finale, open - 1, arr, dp);
  30.         two = helper(val + 1, j, finale, open + 1, arr, dp);
  31.         return dp[val][open] = (one%mod + two%mod)%mod;
  32.         }
  33.     }
  34.  
  35. int main()
  36. {
  37. ll t; cin >> t;
  38. while(t--)
  39.     {
  40.     ll n,k; cin >> n >> k;
  41.     vector<ll> arr;
  42.     ll dp[400][400];
  43.     memset(dp, -1, sizeof(dp));
  44.     if(k == 0)
  45.         {
  46.         arr.push_back(-1);
  47.         cout << helper(1, 0, 2*n, 0, arr, dp) << endl;
  48.         continue;
  49.         }
  50.     for(ll i = 0 ; i<k ; i++)
  51.         {
  52.         ll t; cin >> t;
  53.         arr.push_back(t);
  54.         }
  55.     cout << helper(1, 0, 2*n, 0, arr, dp) << endl;
  56.     }
  57. }
Success #stdin #stdout 0s 4328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mbaZjF
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 years ago
visibility:
secret

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!