#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
using namespace std;
const int MAX_N = 104;
// 73 点解法
long long mod = 1000000007;
long long N; string S;
int dpl[MAX_N][MAX_N][MAX_N], sl[MAX_N][MAX_N][MAX_N];
int dpr[MAX_N][MAX_N][MAX_N], sr[MAX_N][MAX_N][MAX_N];
int dp1[MAX_N][MAX_N][MAX_N][MAX_N];
int dp2[MAX_N][MAX_N][MAX_N * 2][MAX_N];
void all_init() {
for (int i = 0; i < MAX_N; i++) {
for (int j = 0; j < MAX_N; j++) {
for (int k = 0; k < MAX_N; k++) {
dpl[i][j][k] = 0; sl[i][j][k] = 0;
dpr[i][j][k] = 0; sr[i][j][k] = 0;
for (int l = 0; l < MAX_N * 1; l++) dp1[i][j][l][k] = 0;
for (int l = 0; l < MAX_N * 2; l++) dp2[i][j][l][k] = 0;
}
}
}
}
void solve_1(int pos) {
dp1[pos][pos][0][0] = 1;
for (int i = pos; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (dp1[pos][i][j][k] == 0) continue;
if ((S[i] == '(' || S[i] == 'x') && j >= 0) {
dp1[pos][i + 1][j + 1][max(j + 1, k)] += dp1[pos][i][j][k];
if (dp1[pos][i + 1][j + 1][max(j + 1, k)] >= mod) dp1[pos][i + 1][j + 1][max(j + 1, k)] -= mod;
}
if ((S[i] == ')' || S[i] == 'x') && j >= 1) {
dp1[pos][i + 1][j - 1][max(j - 1, k)] += dp1[pos][i][j][k];
if (dp1[pos][i + 1][j - 1][max(j - 1, k)] >= mod) dp1[pos][i + 1][j - 1][max(j - 1, k)] -= mod;
}
}
}
}
for (int i = pos; i <= N; i++) {
for (int j = 0; j <= N; j++) {
for (int k = N; k >= 0; k--) {
dp1[pos][i][j][k] += dp1[pos][i][j][k + 1];
if (dp1[pos][i][j][k] >= mod) dp1[pos][i][j][k] -= mod;
}
}
}
}
void solve_2(int pos) {
dp2[pos][pos][N][0] = 1;
for (int i = pos; i < N; i++) {
for (int j = 0; j <= N * 2; j++) {
for (int k = 0; k < N; k++) {
if (dp2[pos][i][j][k] == 0) continue;
if (S[i] == '(' || S[i] == 'x') {
int val = max(j + 1 - (int)N, k);
dp2[pos][i + 1][j + 1][val] += dp2[pos][i][j][k];
if (dp2[pos][i + 1][j + 1][val] >= mod) dp2[pos][i + 1][j + 1][val] -= mod;
}
if (S[i] == ')' || S[i] == 'x') {
int val = max(j - 1 - (int)N, k);
dp2[pos][i + 1][j - 1][val] += dp2[pos][i][j][k];
if (dp2[pos][i + 1][j - 1][val] >= mod) dp2[pos][i + 1][j - 1][val] -= mod;
}
}
}
}
}
void init() {
// 正しいカッコ列の数を計算する（左側から）
dpl[0][0][0] = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (dpl[i][j][k] == 0) continue;
if ((S[i] == '(' || S[i] == 'x') && j >= 0) {
dpl[i + 1][j + 1][max(j + 1, k)] += dpl[i][j][k];
dpl[i + 1][j + 1][max(j + 1, k)] %= mod;
}
if ((S[i] == ')' || S[i] == 'x') && j >= 1) {
dpl[i + 1][j - 1][max(j - 1, k)] += dpl[i][j][k];
dpl[i + 1][j - 1][max(j - 1, k)] %= mod;
}
}
}
}
// 正しいカッコ列の数を計算する（右側から）
dpr[N][0][0] = 1;
for (int i = N - 1; i >= 0; i--) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (dpr[i + 1][j][k] == 0) continue;
if ((S[i] == ')' || S[i] == 'x') && j >= 0) {
dpr[i][j + 1][max(j + 1, k)] += dpr[i + 1][j][k];
dpr[i][j + 1][max(j + 1, k)] %= mod;
}
if ((S[i] == '(' || S[i] == 'x') && j >= 1) {
dpr[i][j - 1][max(j - 1, k)] += dpr[i + 1][j][k];
dpr[i][j - 1][max(j - 1, k)] %= mod;
}
}
}
}
// 累積和を計算する
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
for (int k = 0; k <= N; k++) sl[i][j][k] = dpl[i][j][k];
for (int k = N; k >= 0; k--) { sl[i][j][k] += sl[i][j][k + 1]; sl[i][j][k] %= mod; }
}
}
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N;j++) {
for (int k = 0; k <= N; k++) sr[i][j][k] = dpr[i][j][k];
for (int k = N; k >= 0; k--) { sr[i][j][k] += sr[i][j][k + 1]; sr[i][j][k] %= mod; }
}
}
for (int i = 0; i <= N; i++) {
solve_1(i);
solve_2(i);
}
}
long long solve2(int maxval, int dep) {
int goal = maxval - dep / 2;
if (goal >= dep - 1) {
long long ans = 0;
for (int i = 0; i <= N - 1; i++) {
if (S[i] == ')') continue;
long long v1 = sl[i][dep - 1][0];
long long v2 = dpr[i + 1][0][maxval - dep];
ans += v1 * v2;
ans %= mod;
}
return ans;
}
else {
long long ans = 0;
for (int i = 0; i <= N - 1; i++) {
if (S[i] == ')') continue;
long long v1 = dpr[i + 1][0][maxval - dep];
for (int j = 0; j < i; j++) {
if (S[j] == ')') continue;
long long v2 = sl[j][goal][0];
long long v3 = (dp1[j + 1][i][dep - 2 - goal][0] - dp1[j + 1][i][dep - 2 - goal][goal] + mod) % mod;
ans += v1 * (v2 * v3 % mod) % mod;
ans %= mod;
}
}
return ans;
}
}
long long solve4(int maxv, int dep) {
long long ans = 0;
int bo = max({ 0, dep, maxv });
int cl_border = (bo + 1) / 2;
int cr_border = (bo + 1) / 2 + dep / 2;
if (cl_border * 2 + maxv + abs(maxv - dep) + min(0, cr_border - dep) * 2 > N) return 0;
for (int i = 0; i <= N - 1; i++) {
if (S[i] == '(') continue;
long long v1 = sl[i][0][cl_border];
for (int j = i + 1; j <= N - 1; j++) {
if (S[j] == ')') continue;
long long v2 = dp2[i + 1][j][dep + N][maxv + 1];
long long v3 = sr[j + 1][0][cr_border - dep];
ans += v1 * (v2 * v3 % mod) % mod;
ans %= mod;
}
}
return ans;
}
int main() {
cin >> N >> S; assert(N <= 100);
if (S.size() % 2 == 1) { cout << "0" << endl; return 0; }
init();
// パターン 1（カッコ列が正しい）
long long ans1 = sl[N][0][0];
// パターン 2（dep > 0、左側が全体）
long long ans2 = 0;
for (int i = N; i >= 1; i -= 2) {
for (int j = i; j <= N; j++) {
if (2 * j - i > N) continue;
ans2 += solve2(j, i);
ans2 %= mod;
}
}
// パターン 4（どちらも全体ではない）
long long ans4 = 0;
for (int i = -1; i <= N; i++) {
for (int j = -N; j <= N; j += 2) {
ans4 += solve4(i, j);
ans4 %= mod;
}
}
// 折り返す
reverse(S.begin(), S.end());
for (int i = 0; i < S.size(); i++) {
if (S[i] == '(') S[i] = ')';
else if (S[i] == ')') S[i] = '(';
}
all_init();
init();
// パターン 3（パターン 2 の逆）
long long ans3 = 0;
for (int i = N; i >= 1; i -= 2) {
for (int j = i; j <= N; j++) {
if (2 * j - i > N) continue;
ans3 += solve2(j, i);
ans3 %= mod;
}
}
// 出力
cout << (ans1 + ans2 + ans3 + ans4) % mod << endl;
return 0;
}
Compilation message
securitygate.cpp: In function 'int main()':
securitygate.cpp:216:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < S.size(); i++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
648 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
648 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
648 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
648 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
648 ms |
1048580 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
