이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 305;
void RADD(int &a, int b) { if ((a += b) >= MOD) a -= MOD; }
int MUL(int a, int b) { return 1ll * a * b % MOD; }
int n;
string a;
int dp_valid[MAXN][MAXN];
int dp_l[MAXN / 2][MAXN][MAXN][2]; // dp[A][pos][bal][done?], A: max height from left without going negitive
int dp_r_one[MAXN][MAXN][MAXN][2]; // dp[A + B/2][pos][bal][fixed?], B: final height
int dp_r_both[MAXN / 2][MAXN][2 * MAXN][3]; // dp[A][pos][bal + n][init/foundA/neg], A: max height from right without going negative
void calc_dp_valid() {
memset(dp_valid, 0, sizeof(dp_valid));
auto dp = dp_valid;
dp[n][0] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= n; j++) {
if (a[i] != ')' && j < n) {
RADD(dp[i][j], dp[i + 1][j + 1]);
}
if (a[i] != '(' && j > 0) {
RADD(dp[i][j], dp[i + 1][j - 1]);
}
}
}
}
void calc_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++) { // pos
for (int j = 0; j <= A; j++) { // bal
for (int k = 0; k < 2; k++) { // done?
if (a[i] != ')' && j < A) {
RADD(dp[i + 1][j + 1][k || j + 1 == A], dp[i][j][k]);
}
if (a[i] != '(' && j > 0) {
RADD(dp[i + 1][j - 1][k], dp[i][j][k]);
}
}
}
}
}
}
void calc_dp_r_one() {
memset(dp_r_one, 0, sizeof(dp_r_one));
for (int M = 0; M <= n; M++) { // M = A + B/2
auto dp = dp_r_one[M];
dp[n][0][!M] = 1;
for (int i = n - 1; i >= 0; i--) { // pos
// not yet fixed M transition
for (int j = 0; j <= n; j++) { // bal
if (a[i] != ')' && j < n) {
RADD(dp[i][j][0], dp[i + 1][j + 1][0]);
}
if (a[i] != '(' && j > 0) {
RADD(dp[i][j][0], dp[i + 1][j - 1][0]);
}
}
// unfixed -> fixed M transition
if (a[i] != ')' && M < n) {
RADD(dp[i][M][1], dp[i + 1][M + 1][0]);
}
if (a[i] != '(' && M > 0) {
RADD(dp[i][M][1], dp[i + 1][M - 1][0]);
}
// fixed M transition, balance mus stay strictly above M
for (int j = M + 1; j <= min(2 * M, n - 1); j++) { // X <= 2A + B = 2M, so X <= 2M
if (a[i] != ')' && j < 2 * M) {
RADD(dp[i][j][1], dp[i + 1][j + 1][1]);
}
if (a[i] != '(' && j > 0){
RADD(dp[i][j][1], dp[i + 1][j - 1][1]);
}
}
}
}
}
void calc_dp_r_both(int not_include_zero) {
memset(dp_r_both, 0, sizeof(dp_r_both));
for (int A = 0; A <= n / 2; A++) { // maximum height viewed from the right
auto dp = dp_r_both[A];
dp[n][n][!(A + not_include_zero)] = 1;
for (int i = n - 1; i >= 0; i--) { // pos
// haven't seen A
for (int j = 0; j <= n; j++) { // bal
if (a[i] != '(' && j < n) {
RADD(dp[i][j + 1 + n][j + 1 == A + not_include_zero], dp[i + 1][j + n][0]);
}
if (a[i] != ')' && j > 0) {
RADD(dp[i][j - 1 + n][0], dp[i + 1][j + n][0]);
}
}
// seen A
for (int j = 0; j <= n; j++) {
if (a[i] != '(') {
RADD(dp[i][j + 1 + n][1], dp[i + 1][j + n][1]);
}
if (a[i] != ')') {
RADD(dp[i][j - 1 + n][1 + !j], dp[i + 1][j + n][1]);
}
}
// gone negative
for (int j = - n; j <= min(2 * A, n - 1); j++) {
if (a[i] != '(' && j < 2 * A) {
RADD(dp[i][j + 1 + n][2], dp[i + 1][j + n][2]);
}
if (a[i] != ')' && j > - n) {
RADD(dp[i][j - 1 + n][2], dp[i + 1][j + n][2]);
}
}
}
}
}
int invalid_one() {
int res = 0;
for (int A = 0; A <= n / 2; A++) { // maximum before going negative from the left
for (int B = 2; B <= n; B += 2) { // B = final height on the right
for (int pos = 0; pos < n; pos += 2) {
if (a[pos] == '(') continue;
int val = A >= B / 2 ? dp_valid[pos + 1][B - 1] : dp_r_one[A + B / 2][pos + 1][B - 1][1];
RADD(res, MUL(dp_l[A][pos][0][1], val));
}
}
}
return res;
}
int invalid_both() {
int res = 0;
for (int A = 0; A <= n / 2; A++) {
for (int B = - n + 2; B < n; B += 2) {
if (A + B / 2 < 0 || A + abs(B / 2) >= n / 2) continue;
for (int pos = 0; pos < n; pos += 2) {
if (a[pos] == '(') continue;
RADD(res, MUL(dp_l[A][pos][0][1], dp_r_both[A + B / 2][pos + 1][B - 1 + n][2]));
}
}
}
return res;
}
int Solve() {
if (n & 1) return 0;
calc_dp_valid();
calc_dp_l();
calc_dp_r_one();
calc_dp_r_both(0);
int res = dp_valid[0][0];
RADD(res, invalid_one());
RADD(res, invalid_both());
reverse(begin(a), end(a));
for (int i = 0; i < n; i++) {
if (a[i] == '(') {
a[i] = ')';
} else if (a[i] == ')') {
a[i] = '(';
}
}
calc_dp_valid();
calc_dp_l();
calc_dp_r_one();
calc_dp_r_both(1);
RADD(res, invalid_one());
RADD(res, invalid_both());
return res;
}
int main() {
cin >> n >> a;
cout << Solve() << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |