Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define task "TGBRACKETS"
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- using ll = long long;
- using ld = long double;
- constexpr int N = 5e2 + 5;
- constexpr int mod = 1e9 + 7;
- int n;
- string s;
- int dp[N][N][N / 2];
- void Read()
- {
- cin >> n >> s;
- s = " " + s;
- }
- #define Match(x, y) (x != y)
- int f(int x, int y, int sum)
- {
- int &ans = dp[x][y][sum];
- if (ans != -1)
- return ans;
- ans = 0;
- if (x >= y)
- return ans = 1;
- ans = ((f(x + 1, y, sum) + f(x, y - 1, sum)) % mod - f(x + 1, y - 1, sum)) % mod;
- if (Match(s[x], s[y]) && (s[x] == '(' || sum > 0))
- (ans += f(x + 1, y - 1, sum + (s[x] == '(' ? 1 : -1))) %= mod;
- return ans;
- }
- void Solve()
- {
- memset(dp, -1, sizeof dp);
- cout << (f(1, n, 0) - 1 + mod) % mod;
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- if (fopen(task ".INP", "r"))
- {
- freopen(task ".INP", "r", stdin);
- freopen(task ".OUT", "w", stdout);
- }
- Read();
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement