#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define debug(x) cout << #x << "= " << x << ", "
#define ll long long
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define SZ(x) (int) x.size()
#define wall cout << endl;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 605 , maxl = 1205 , mod = 1e9 + 7;
int n , ar[maxl] , fac[maxl] , dp[maxl][maxn] , f[maxn] , m2[maxn] , frev[maxl];
inline int mpo(int a , int b)
{
int res = 1;
while(b != 0)
{
if(b & 1) res = 1LL * res * a % mod;
b >>= 1;
a = 1LL * a * a % mod;
}
return res;
}
inline int C(int a , int b)
{
if(b > a || b < 0 || a < 0) return 0;
int res = 1LL * fac[a] * frev[b] % mod;
res = 1LL * res * frev[a - b] % mod;
return res;
}
int32_t main()
{
fast;
cin >> n;
int m = n * 2;
for(int i = 0 ; i < n ; i++)
{
int x ; cin >> x;
ar[x] = 1;
}
fac[0] = fac[1] = frev[0] = frev[1] = 1;
for(int i = 2 ; i < maxl ; i++)
{
fac[i] = 1LL * fac[i - 1] * i % mod;
frev[i] = mpo(fac[i] , mod - 2);
}
m2[0] = 1;
for(int i = 1 ; i < maxn ; i++) m2[i] = m2[i - 1] * 2 % mod;
f[0] = 1;
for(int i = 1 ; i < maxn ; i++)
{
for(int j = 0 ; 2 * j <= i ; j++)
{
int tmp = (C(2 * j , j) - C(2 * j , j - 1) + mod) % mod;
tmp = 1LL * tmp * C(i , 2 * j) % mod;
tmp = 1LL * tmp * m2[i - 2 * j] % mod;
tmp = 1LL * tmp * fac[i] % mod;
f[i] = (f[i] + tmp) % mod;
}
}
if(ar[m] == 0)
{
cout << 0 << endl; return 0;
}
int cntz = 0 , cnto = 1;
dp[m][0] = 1; dp[m][1] = 2;
for(int i = m - 1 ; i > 0 ; i--)
{
if(ar[i] == 0) cntz++;
else cnto++;
if(ar[i] == 0)
for(int j = cntz ; j <= cnto ; j++)
dp[i][j] = 1LL * dp[i + 1][j] * (j - cntz + 1) % mod;
else
{
for(int j = cntz ; j <= cnto ; j++)
{
dp[i][j] = dp[i + 1][j];
for(int k = cntz ; k < j ; k++)
{
int tmp = 1LL * f[j - k - 1] * C(cnto - k - 1 , j - k - 1) % mod;
tmp = 1LL * tmp * (j - k + 1) % mod;
tmp = 1LL * tmp * dp[i + 1][k] % mod;
dp[i][j] = (dp[i][j] + tmp) % mod;
}
}
}
}
int ans = mpo(m2[n] , mod - 2);
ans = 1LL * ans * dp[1][n] % mod;
cout << ans << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
352 KB |
Output is correct |
4 |
Correct |
3 ms |
352 KB |
Output is correct |
5 |
Correct |
2 ms |
352 KB |
Output is correct |
6 |
Correct |
3 ms |
352 KB |
Output is correct |
7 |
Correct |
3 ms |
352 KB |
Output is correct |
8 |
Correct |
3 ms |
352 KB |
Output is correct |
9 |
Correct |
3 ms |
360 KB |
Output is correct |
10 |
Correct |
3 ms |
352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
352 KB |
Output is correct |
4 |
Correct |
3 ms |
352 KB |
Output is correct |
5 |
Correct |
2 ms |
352 KB |
Output is correct |
6 |
Correct |
3 ms |
352 KB |
Output is correct |
7 |
Correct |
3 ms |
352 KB |
Output is correct |
8 |
Correct |
3 ms |
352 KB |
Output is correct |
9 |
Correct |
3 ms |
360 KB |
Output is correct |
10 |
Correct |
3 ms |
352 KB |
Output is correct |
11 |
Correct |
3 ms |
608 KB |
Output is correct |
12 |
Correct |
3 ms |
608 KB |
Output is correct |
13 |
Correct |
4 ms |
612 KB |
Output is correct |
14 |
Correct |
3 ms |
340 KB |
Output is correct |
15 |
Correct |
3 ms |
340 KB |
Output is correct |
16 |
Correct |
3 ms |
616 KB |
Output is correct |
17 |
Correct |
3 ms |
340 KB |
Output is correct |
18 |
Correct |
3 ms |
596 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
340 KB |
Output is correct |
3 |
Correct |
3 ms |
352 KB |
Output is correct |
4 |
Correct |
3 ms |
352 KB |
Output is correct |
5 |
Correct |
2 ms |
352 KB |
Output is correct |
6 |
Correct |
3 ms |
352 KB |
Output is correct |
7 |
Correct |
3 ms |
352 KB |
Output is correct |
8 |
Correct |
3 ms |
352 KB |
Output is correct |
9 |
Correct |
3 ms |
360 KB |
Output is correct |
10 |
Correct |
3 ms |
352 KB |
Output is correct |
11 |
Correct |
3 ms |
608 KB |
Output is correct |
12 |
Correct |
3 ms |
608 KB |
Output is correct |
13 |
Correct |
4 ms |
612 KB |
Output is correct |
14 |
Correct |
3 ms |
340 KB |
Output is correct |
15 |
Correct |
3 ms |
340 KB |
Output is correct |
16 |
Correct |
3 ms |
616 KB |
Output is correct |
17 |
Correct |
3 ms |
340 KB |
Output is correct |
18 |
Correct |
3 ms |
596 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
596 KB |
Output is correct |
21 |
Correct |
5 ms |
3156 KB |
Output is correct |
22 |
Correct |
4 ms |
3156 KB |
Output is correct |
23 |
Correct |
5 ms |
3156 KB |
Output is correct |
24 |
Correct |
10 ms |
3140 KB |
Output is correct |
25 |
Correct |
2 ms |
340 KB |
Output is correct |
26 |
Correct |
6 ms |
3156 KB |
Output is correct |
27 |
Correct |
2 ms |
340 KB |
Output is correct |
28 |
Correct |
4 ms |
3156 KB |
Output is correct |
29 |
Correct |
3 ms |
340 KB |
Output is correct |
30 |
Correct |
454 ms |
3116 KB |
Output is correct |
31 |
Correct |
250 ms |
3168 KB |
Output is correct |
32 |
Correct |
348 ms |
3092 KB |
Output is correct |
33 |
Correct |
420 ms |
3148 KB |
Output is correct |
34 |
Correct |
224 ms |
3092 KB |
Output is correct |
35 |
Correct |
335 ms |
3052 KB |
Output is correct |
36 |
Correct |
413 ms |
3212 KB |
Output is correct |