#include <algorithm>
#include <cstring>
#include <cstdio>
using ll = long long;
constexpr int MOD = 1e9 + 7;
inline void add(int &x, const int &y) { (x += y) >= MOD ? (x -= MOD) : 0; }
int n, arr[305], any[305][305], dp_l[155][305][305][2], dp_r[305][305][605][3];
inline void init_any()
{
memset(any, 0, sizeof(any));
any[n][0] = 1;
for (int i = n - 1; i >= 0; i--)
{
for (int j = 0; j <= n; j++)
{
if (!any[i + 1][j])
continue;
if (arr[i] != +1 && j < n)
add(any[i][j + 1], any[i + 1][j]);
if (arr[i] != -1 && j > 0)
add(any[i][j - 1], any[i + 1][j]);
}
}
}
inline void init_dp_l()
{
memset(dp_l, 0, sizeof(dp_l));
for (int a = 0; a < n / 2; a++)
{
auto dp = dp_l[a];
dp[0][0][!a] = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= a; j++)
{
for (int x = 0; x < 2; x++)
{
if (!dp[i][j][x])
continue;
if (arr[i] != -1 && j < a)
add(dp[i + 1][j + 1][x || j + 1 == a], dp[i][j][x]);
if (arr[i] != +1 && j > 0)
add(dp[i + 1][j - 1][x], dp[i][j][x]);
}
}
}
}
}
inline int solve_1()
{
memset(dp_r, 0, sizeof(dp_r));
for (int a = 0; a < n; a++)
{
auto dp = dp_r[a];
dp[n][0][!a] = 1;
for (int i = n - 1; i >= 0; i--)
{
for (int j = 0; j <= n; j++)
{
if (!dp[i + 1][j][0])
continue;
if (arr[i] != +1 && j < n)
add(dp[i][j + 1][0], dp[i + 1][j][0]);
if (arr[i] != -1 && j > 0)
add(dp[i][j - 1][0], dp[i + 1][j][0]);
}
if (arr[i] != -1 && a < n)
add(dp[i][a][1], dp[i + 1][a + 1][0]);
if (arr[i] != +1 && a > 0)
add(dp[i][a][1], dp[i + 1][a - 1][0]);
for (int j = 0; j <= std::min(a * 2, n - 1); j++)
{
if (!dp[i + 1][j][1])
continue;
if (arr[i] != +1 && j >= a)
add(dp[i][j + 1][1], dp[i + 1][j][1]);
if (arr[i] != -1 && j >= a + 2)
add(dp[i][j - 1][1], dp[i + 1][j][1]);
}
}
}
int res = 0;
for (int a = 0; a <= n / 2; a++)
{
for (int b = 1; a + b <= n / 2; b++)
{
for (int pos = 0; pos < n; pos += 2)
{
if (arr[pos] == 1)
continue;
int val = a >= b ? any[pos + 1][2 * b - 1] :
dp_r[a + b][pos + 1][2 * b - 1][1];
res = (res + (ll)dp_l[a][pos][0][1] * val) % MOD;
}
}
}
return res;
}
inline int solve_2(int t)
{
memset(dp_r, 0, sizeof(dp_r));
for (int a = 0; a < n / 2; a++)
{
auto dp = dp_r[a];
dp[n][n][!(a + t)] = 1;
for (int i = n - 1; i >= 0; i--)
{
for (int j = 0; j <= n; j++)
{
if (!dp[i + 1][j + n][0])
continue;
if (arr[i] != +1 && j < n)
add(dp[i][j + 1 + n][j + 1 == a + t], dp[i + 1][j + n][0]);
if (arr[i] != -1 && j > 0)
add(dp[i][j - 1 + n][0], dp[i + 1][j + n][0]);
}
for (int j = 0; j <= n; j++)
{
if (!dp[i + 1][j + n][1])
continue;
if (arr[i] != +1)
add(dp[i][j + 1 + n][1], dp[i + 1][j + n][1]);
if (arr[i] != -1)
add(dp[i][j - 1 + n][1 + !j], dp[i + 1][j + n][1]);
}
for (int j = -n; j <= std::min(a * 2, n - 1); j++)
{
if (!dp[i + 1][j + n][2])
continue;
if (arr[i] != +1 && j < a * 2)
add(dp[i][j + 1 + n][2], dp[i + 1][j + n][2]);
if (arr[i] != -1 && j > -n)
add(dp[i][j - 1 + n][2], dp[i + 1][j + n][2]);
}
}
}
int res = 0;
for (int a = 0; a <= n / 2; a++)
{
for (int b = -n / 2 + 1; b < n / 2; b++)
{
if (a + b < 0 || a + (b < 0 ? -b : b) >= n / 2)
continue;
for (int pos = 0; pos < n; pos += 2)
{
if (arr[pos] == 1)
continue;
res = (res + (ll)dp_l[a][pos][0][1] *
dp_r[a + b][pos + 1][b * 2 - 1 + n][2]) % MOD;
}
}
}
return res;
}
char str[305];
int main()
{
// freopen("JOISC2018-D3T3.in", "r", stdin);
scanf("%d%s", &n, str);
for (int i = 0; i < n; i++)
arr[i] = str[i] == '(' ? 1 : str[i] == ')' ? -1 : 0;
init_any();
int ans = any[0][0];
init_dp_l();
add(ans, solve_1());
add(ans, solve_2(0));
std::reverse(arr, arr + n);
for (int i = 0; i < n; i++)
arr[i] = -arr[i];
init_any();
init_dp_l();
add(ans, solve_1());
add(ans, solve_2(1));
printf("%d\n", ans);
return 0;
}
Compilation message
securitygate.cpp: In function 'int main()':
securitygate.cpp:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%s", &n, str);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5196 ms |
540164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5196 ms |
540164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5196 ms |
540164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5196 ms |
540164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5196 ms |
540164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
