Source Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
const int N = 1e6 + 10, mod = 7 + 1e9;
const ll oo = 1e9, ooo = 1e9;
double eps = 1e-9;

ll n, dp[1001][1001][2][2][2][2][2];
ll cal(int i, int o, bool e, int p1, int p2, int p3, int p4){
  if(i == n){
    return o == 0 && e;
  }
  ll &dp = ::dp[i][o][e][p1][p2][p3][p4];
  if(~dp)
    return dp;
  bool ex = p1 == 1 && p2 == 1 && p3 == 1 && p4 == 0;
  dp = cal(i+1, o+1, e, p2, p3, p4, 1);
  if(o > 0)
    dp += cal(i+1, o-1, ex || e, p2, p3, p4, 0);
  return dp % mod;
}
void realityisoftendisappointing(){
  cin >> n;
  memset(dp, -1, sizeof dp);
  cout << cal(0, 0, 0, 0, 0, 0, 0);// the pattern starts with 1 so it's ok
  return;
}

int main()
{
  ios_base::sync_with_stdio(false); 
  cin.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
#endif  
  int t = 1;
  // cin >> t;
  while (t--)
    realityisoftendisappointing();
}
Copy
Bracket Sequence fortyfive
GNU G++17
397 ms
252.1 MB
Accepted