#include <bits/stdc++.h>
using namespace std;
const int N = 503;
int md;
int dp[2 * N][N][N][6][2][2];
int add(int x, int y) {
return x + y < md ? x + y : x + y - md;
}
void ckadd(int& x, int y) {
x = add(x, y);
}
int mul(int x, int y) {
return x * 1LL * y % md;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n >> md;
dp[0][0][0][2][0][0] = 1;
for (int pos = 1; pos <= 2 * n; pos++) {
for (int bal = 0; bal <= n; bal++) {
for (int bef = 0; bef <= n; bef++) {
for (int rd = 0; rd < 6; rd++) {
for (int o = 0; o < 2; o++) {
for (int b = 0; b < 2; b++) {
if (dp[pos - 1][bal][bef][rd][o][b] == 0) {
continue;
}
int open = bal;
int close = open - bal;
{
// take open bracket
int new_bal = bal + 1;
int new_bef = bef;
int new_rd = rd;
int new_o = 1;
int new_b = (o == 1 ? b : 0);
if (o == 0) {
new_rd--;
}
ckadd(dp[pos][new_bal][new_bef][new_rd][new_o][new_b], dp[pos - 1][bal][bef][rd][o][b]);
}
if (bal > 0) {
// take close bracket
if (o == 1) {
// match last bad greedy bracket
if (b == 1) {
int new_bal = bal - 1;
int new_bef = bef - 1;
int new_rd = rd;
int new_o = 0;
int new_b = 0;
ckadd(dp[pos][new_bal][new_bef][new_rd][new_o][new_b], dp[pos - 1][bal][bef][rd][o][b]);
} else {
int new_bal = bal - 1;
int new_bef = open - 1;
int new_rd = min(5, rd + 1);
int new_o = 0;
int new_b = 0;
ckadd(dp[pos][new_bal][new_bef][new_rd][new_o][new_b], dp[pos - 1][bal][bef][rd][o][b]);
}
}
// match with bracket that is not last bad greedy bracket
{
// match with bracket before last opt greedy
int new_bal = bal - 1;
int new_bef = bef - 1;
int new_rd = rd;
int new_o = o;
int new_b = b;
int ft = bef - (o == 1 && b == 1);
ckadd(dp[pos][new_bal][new_bef][new_rd][new_o][new_b], mul(dp[pos - 1][bal][bef][rd][o][b], ft));
}
{
// match with bracket after last opt greedy
int new_bal = bal - 1;
int new_bef = open - 1;
int new_rd = min(5, rd + 1);
int new_o = o;
int new_b = (o == 1 ? 1 : 0);
int ft = (open - bef) - (o == 1 && b == 0);
ckadd(dp[pos][new_bal][new_bef][new_rd][new_o][new_b], mul(dp[pos - 1][bal][bef][rd][o][b], ft));
}
}
}
}
}
}
}
}
int res = 0;
for (int bef = 0; bef <= n; bef++) {
for (int rd = 3; rd < 6; rd++) {
ckadd(res, dp[2 * n][0][bef][rd][0][0]);
}
}
cout << res << '\n';
return 0;
}
Compilation message
festival2.cpp: In function 'int main()':
festival2.cpp:38:19: warning: unused variable 'close' [-Wunused-variable]
38 | int close = open - bal;
| ^~~~~
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
