This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// oooo
/*
be hengam shena mesle y dasto pa cholofti ~
bepa to masire dahane koose neyofti ~
;Amoo_Hasan;
*/
#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
typedef long double ld;
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
const ll inf = 1e18, N = 650, mod = 1e9 + 7, pr = 1000696969;
int a[N];
ll dp[N], sf[N][N];
ll fac[N], rfac[N];
bool mark[N];
ll poww(ll x, ll y) {
ll res = 1;
for(; y; y /= 2, x = x * x % mod)
if(y & 1) {
res = res * x % mod;
}
return res;
}
void pre() {
fac[0] = 1;
for(int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;
for(int i = 0; i < N; i++) rfac[i] = poww(fac[i], mod - 2);
}
ll choose(ll x, ll y) {
if(x > y) return 0;
if(x == y) return 1;
ll ans = fac[y];
ans *= rfac[x];
ans %= mod;
ans *= rfac[y - x];
ans %= mod;
return ans;
}
int main() {
ios :: sync_with_stdio(0), cin.tie(0);
pre();
int n; cin >>n;
for(int i = 1; i <= n; i++) cin >>a[i], mark[a[i]] = 1;
dp[0] = 1;
for(int len = 1; len <= n; len++) {
for(int j = 0; j < len; j++) {
ll val = dp[j] * dp[len - j - 1];
val %= mod;
val *= choose(j, len - 1);
val %= mod;
val *= j + 2; val %= mod;
dp[len] += val;
dp[len] %= mod;
}
}
int c0 = 0, c1 = 0;
sf[2 * n + 1][0] = 1;
for(int i = 2 * n; i > 0; i--) {
if(mark[i] == 0) {
for(int R = 0; R <= c1; R++) {
sf[i][R] = sf[i + 1][R] * (max(0, R - c0));
sf[i][R] %= mod;
}
c0++;
continue;
}
for(int R = 0; R <= c1 + 1; R++) {
int k = c1 - R + 1;
sf[i][R] = sf[i + 1][R];
sf[i][R] %= mod;
for(int j = 0; j < R; j++) {
ll val = dp[j] * sf[i + 1][R - j - 1];
val %= mod;
val *= choose(j, c1 - (R - j) + 1);
val %= mod;
val *= j + 2;
val %= mod;
sf[i][R] += val;
sf[i][R] %= mod;
}
}
c1++;
}
ll ans = sf[1][n];
ans *= poww(poww(2, n), mod - 2);
ans %= mod;
cout<<ans;
return 0;
}
Compilation message (stderr)
ruins3.cpp: In function 'int main()':
ruins3.cpp:88:8: warning: unused variable 'k' [-Wunused-variable]
88 | int k = c1 - R + 1;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |