#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 120;
const ll mod = 1e9 + 7;
int n, a[maxn];
int b[2 * maxn];
ll dp[2 * maxn][maxn][maxn], comb[maxn][maxn];
ll fp[maxn][maxn], fac[maxn];
ll power(ll base, ll st)
{
ll res = 1;
while(st > 0)
{
if (st % 2 == 1)
res = (res * base) % mod;
base = (base * base) % mod;
st /= 2;
}
return res;
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
b[a[i]] = 1;
}
if (a[n] != 2 * n)
{
cout << 0 << endl;
return;
}
comb[0][0] = 1;
for (int i = 1; i <= n; i ++)
{
comb[i][0] = 1;
for (int j = 1; j <= n; j ++)
{
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
if (comb[i][j] >= mod)
comb[i][j] -= mod;
}
}
fp[0][0] = fp[1][0] = 1;
for (int i = 2; i <= n; i ++)
{
fp[i][0] = fp[i - 1][0];
for (int j = 1; j <= i; j ++)
{
fp[i][j] = fp[i - 1][j] + fp[i - 2][j - 1];
fp[i][j] %= mod;
}
}
fac[0] = 1;
for (int i = 1; i <= n; i ++)
{
fac[i] = (fac[i - 1] * (ll)(i)) % mod;
fac[i] %= mod;
}
ll dv = power(2, mod - 2);
for (int i = 0; i <= n; i ++)
for (int j = 0; j <= i; j ++)
{
int lf = i - j;
fp[i][j] *= fac[i];
fp[i][j] %= mod;
fp[i][j] *= power(dv, j);
fp[i][j] %= mod;
}
//cout << "fp " << fp[2][1] << endl;
//return;
dp[2 * n][1][0] = 1;
if (n != 1)
dp[2 * n][0][0] = 1;
int down = 0, up = 1;
for (int i = 2 * n - 1; i > 0; i --)
{
if (b[i] == 0)
down ++;
else
up ++;
if (b[i] == 0)
{
for (int j = 0; j <= up; j ++)
{
for (int d = 0; d <= j; d ++)
{
ll lf_to_start = (j - d) - (j + (down - 1) - 2 * d);
ll lf_to_fill = (j - d) - lf_to_start;
if (lf_to_fill < 0 || lf_to_start < 0)
continue;
dp[i][j][d + 1] += dp[i + 1][j][d] * lf_to_fill;
dp[i][j][d + 1] %= mod;
dp[i][j][d] += dp[i + 1][j][d] * lf_to_start;
dp[i][j][d] %= mod;
}
}
}
else
{
for (int j = 0; j <= up; j ++)
{
for (int t = j; t <= up; t ++)
{
if (up == n && t != up)
continue;
for (int d = 0; d <= up; d ++)
{
for (int k = d; k <= up; k ++)
{
ll dt = t - j;
ll dk = k - d;
if (dt != 0)
{
/**ll ways = comb[up - j - 1][dt - 1] * fp[dt][dk];
ways %= mod;
dp[i][t][k] += dp[i + 1][j][d] * ways;
dp[i][t][k] %= mod;*/
/**if (i == 3 && t == 3 && k == 1)
{
cout << "from " << i + 1 << " " << j << " " << d << " ways " << ways << endl;
}*/
/// without bind
ll ways = comb[up - j - 1][dt - 1] * fp[dt - 1][dk];
ways %= mod;
ll no_band = (dt - dk) - ((dt - 1) - 2 * dk);
ways = (ways * no_band) % mod;
dp[i][t][k] += dp[i + 1][j][d] * ways;
dp[i][t][k] %= mod;
if (dk > 0)
{
ways = comb[up - j - 1][dt - 1] * fp[dt - 1][dk - 1];
ways %= mod;
ll with_band = ((dt - 1) - 2 * (dk - 1));
/**if (i == 3 && t == 3 && k == 2)
{
cout << "no band " << no_band << endl;
cout << "with band " << with_band << endl;
cout << "dt " << dt << endl;
cout << i + 1 << " " << j << " " << d << " " << dp[i + 1][j][d] << " " << ways << endl;
}*/
ways *= with_band;
ways %= mod;
dp[i][t][k] += dp[i + 1][j][d] * ways;
dp[i][t][k] %= mod;
}
}
else
{
if (k == d)
{
dp[i][j][d] += dp[i + 1][j][d];
dp[i][j][d] %= mod;
}
}
}
}
}
}
}
cout << "---------------" << endl;
for (int j = 0; j <= up; j ++)
for (int d = 0; d <= j; d ++)
{
cout << "state " << i << " " << j << " " << d << " = " << dp[i][j][d] << endl;
}
}
ll res = dp[1][n][n];
//res = (res * dv) % mod;
cout << res << endl;
}
int main()
{
speed();
int t = 1;
///cin >> t;
while(t --)
solve();
return 0;
}
/**
13
3 7 9 12 13 15 16 18 22 23 24 25 26
*/
Compilation message
ruins3.cpp: In function 'void solve()':
ruins3.cpp:86:17: warning: unused variable 'lf' [-Wunused-variable]
86 | int lf = i - j;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
