Source Code
#include "bits/stdc++.h"

using namespace std;

template<int MOD>
struct Integral {
  int v_ = 0;
 
  // Implicit conversion is allowed.
  Integral(int v) : v_(norm(v)) {}
  Integral(long long v) : v_(norm(v)) {}
  Integral(unsigned int v) : v_(norm(v)) {}
  Integral(unsigned long long v) : v_(norm(v)) {}
  Integral() = default;
  ~Integral() = default;
 
  template<typename T> T norm(T v) const {
    if constexpr(sizeof(T) > sizeof(MOD)) {
      v %= MOD;
      if (v < 0) v += MOD;
    } else {
      if (v >= MOD) v -= MOD;
      if (v < 0) v += MOD;
      if (v >= MOD || v < 0) {
        v %= MOD;
        if (v < 0) v += MOD;
      }
    }
    return v;
  }
 
  int val() const { return v_; }
  Integral& operator+=(const Integral& rhs) { v_ += rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
  Integral& operator-=(const Integral& rhs) { v_ += MOD - rhs.val(); if (v_ >= MOD) v_ -= MOD; return *this; }
  Integral& operator*=(const Integral& rhs) { v_ = v_ * 1LL * rhs.val() % MOD; return *this; }
  Integral& operator/=(const Integral& rhs) { v_ = v_ * 1LL * rhs.inv().val() % MOD; return *this; }
  Integral operator+(const Integral& rhs) const { Integral ret = *this; return ret += rhs; }
  Integral operator-(const Integral& rhs) const { Integral ret = *this; return ret -= rhs; }
  Integral operator*(const Integral& rhs) const { Integral ret = *this; return ret *= rhs; }
  Integral operator/(const Integral& rhs) const { Integral ret = *this; return ret /= rhs; }
  bool operator==(const Integral& rhs) const { return val() == rhs.val(); }
  bool operator!=(const Integral& rhs) const { return !(*this == rhs); }
  const Integral operator-() const { return Integral(-val()); }
  const Integral& operator++() { v_ += 1; if (v_ >= MOD) v_ -= MOD; return *this; }
  const Integral operator++(int) { Integral ret = *this; ++(*this); return ret; }
  const Integral& operator--() { v_ += MOD - 1; if (v_ >= MOD) v_ -= MOD; return *this; }
  const Integral operator--(int) { Integral ret = *this; --(*this); return ret; }
 
  Integral power(long long b) const {
    long long ret = 1 % MOD, a = v_;
    for ( ; b; b >>= 1, a = a * a % MOD) if (b & 1) ret = ret * a % MOD;
    return ret;
  }
  Integral inv() const { return power(MOD - 2); }
 
  std::string to_string() const { return std::string("{") + std::to_string(val()) + "}"; }
};
 
const int MOD = 1e9 + 7;
using Mint = Integral<MOD>;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  string p = "((())";
  int m = p.size();
  vector<vector<vector<Mint>>> dp(n + 1, vector<vector<Mint>>(m + 1, vector<Mint>(n / 2 + 1, 0)));
  dp[0][0][0] = 1;

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= m; ++j) {
      for (int balance = 0; 2 * balance <= n; ++balance) {
        if (j == m) {
          dp[i + 1][j][balance + 1] += dp[i][j][balance];
          if (balance > 0) {
            dp[i + 1][j][balance - 1] += dp[i][j][balance];
          }
        } else if (p[j] == '(') {
          dp[i + 1][j + 1][balance + 1] += dp[i][j][balance];
          if (balance > 0) {
            dp[i + 1][0][balance - 1] += dp[i][j][balance];
          }
        } else {
          if (p[j - 1] == '(') {
            dp[i + 1][j][balance + 1] += dp[i][j][balance];
          } else {
            dp[i + 1][1][balance + 1] += dp[i][j][balance];
          }
          if (balance > 0) {
            dp[i + 1][j + 1][balance - 1] += dp[i][j][balance];
          }
        }
      }
    }
  }

  cout << dp[n][m][0].val() << '\n';

  return 0;
}
Copy
Bracket Sequence abdulrahman_aj
GNU G++17
3 ms
876 KB
Runtime Error