#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int maxn = 1210;
const int mod = 1e9+7;
inline int bpow(int x, int y)
{
int ans = 1;
while(y > 0)
{
if(y & 1)
ans = 1ll*ans*x % mod;
x = 1ll*x*x % mod;
y >>= 1;
}
return ans;
}
int MK(int a, int b)
{
a += b;
if(a >= mod) return a-mod;
if(a < 0) return a+mod;
return a;
}
int dp[maxn];
int prf[maxn][maxn];
int cmb[maxn][maxn];
bool one[maxn];
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cmb[0][0] = 1;
for(int i = 1; i < maxn; i++)
{
cmb[i][0] = 1;
for(int j = 1; j <= i; j++)
cmb[i][j] = MK(cmb[i-1][j], cmb[i-1][j-1]);
}
int n; cin >> n;
for(int i = 0; i < n; i++)
{
int x; cin >> x; x--;
one[x] = true;
}
dp[0] = 1;
for(int i = 1; i <= n; i++)
for(int j = 0; j < i; j++)
dp[i] = MK(dp[i], 1ll*dp[j]*dp[i-1-j]%mod * cmb[i-1][j]%mod * (i-j+1) % mod );
prf[2*n][0] = 1;
int c1 = 0;
for(int i = 2*n-1; i >= 0; i--)
{
c1 += one[i];
if(one[i])
{
for(int j = 0; j <= c1; j++)
{
prf[i][j] = prf[i+1][j];
for(int k = 0; k < j; k++)
{
prf[i][j] = MK(prf[i][j], 1ll*prf[i+1][k]*dp[j-k-1]%mod * cmb[c1-k-1][j-k-1]%mod * (j-k+1) % mod);
//cerr << k << " " << cmb[c1-k-1][j-k-1] << " " << prf[i+1][k] << " " << dp[j-k-1] << " " << (j-k+1) << endl;
}
}
}
else
{
for(int j = 0; j <= c1; j++)
prf[i][j] = 1ll*prf[i+1][j]*max(0,j-(2*n-i-1-c1))%mod;
}
//for(int j = 0; j <= c1; j++) cerr << prf[i][j] << " ";
//cerr << endl;
}
cout << (1ll*prf[1][n] * bpow(bpow(2, n),mod-2) % mod) << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
6084 KB |
Output is correct |
2 |
Correct |
5 ms |
5976 KB |
Output is correct |
3 |
Correct |
6 ms |
5976 KB |
Output is correct |
4 |
Correct |
5 ms |
5964 KB |
Output is correct |
5 |
Correct |
5 ms |
5968 KB |
Output is correct |
6 |
Correct |
6 ms |
6092 KB |
Output is correct |
7 |
Correct |
6 ms |
6008 KB |
Output is correct |
8 |
Correct |
5 ms |
6092 KB |
Output is correct |
9 |
Correct |
5 ms |
5972 KB |
Output is correct |
10 |
Correct |
6 ms |
6092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
6084 KB |
Output is correct |
2 |
Correct |
5 ms |
5976 KB |
Output is correct |
3 |
Correct |
6 ms |
5976 KB |
Output is correct |
4 |
Correct |
5 ms |
5964 KB |
Output is correct |
5 |
Correct |
5 ms |
5968 KB |
Output is correct |
6 |
Correct |
6 ms |
6092 KB |
Output is correct |
7 |
Correct |
6 ms |
6008 KB |
Output is correct |
8 |
Correct |
5 ms |
6092 KB |
Output is correct |
9 |
Correct |
5 ms |
5972 KB |
Output is correct |
10 |
Correct |
6 ms |
6092 KB |
Output is correct |
11 |
Correct |
6 ms |
6436 KB |
Output is correct |
12 |
Correct |
6 ms |
6476 KB |
Output is correct |
13 |
Correct |
7 ms |
6476 KB |
Output is correct |
14 |
Correct |
6 ms |
6476 KB |
Output is correct |
15 |
Correct |
6 ms |
6476 KB |
Output is correct |
16 |
Correct |
6 ms |
6604 KB |
Output is correct |
17 |
Correct |
6 ms |
6364 KB |
Output is correct |
18 |
Correct |
6 ms |
6376 KB |
Output is correct |
19 |
Correct |
6 ms |
6476 KB |
Output is correct |
20 |
Correct |
6 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
6084 KB |
Output is correct |
2 |
Correct |
5 ms |
5976 KB |
Output is correct |
3 |
Correct |
6 ms |
5976 KB |
Output is correct |
4 |
Correct |
5 ms |
5964 KB |
Output is correct |
5 |
Correct |
5 ms |
5968 KB |
Output is correct |
6 |
Correct |
6 ms |
6092 KB |
Output is correct |
7 |
Correct |
6 ms |
6008 KB |
Output is correct |
8 |
Correct |
5 ms |
6092 KB |
Output is correct |
9 |
Correct |
5 ms |
5972 KB |
Output is correct |
10 |
Correct |
6 ms |
6092 KB |
Output is correct |
11 |
Correct |
6 ms |
6436 KB |
Output is correct |
12 |
Correct |
6 ms |
6476 KB |
Output is correct |
13 |
Correct |
7 ms |
6476 KB |
Output is correct |
14 |
Correct |
6 ms |
6476 KB |
Output is correct |
15 |
Correct |
6 ms |
6476 KB |
Output is correct |
16 |
Correct |
6 ms |
6604 KB |
Output is correct |
17 |
Correct |
6 ms |
6364 KB |
Output is correct |
18 |
Correct |
6 ms |
6376 KB |
Output is correct |
19 |
Correct |
6 ms |
6476 KB |
Output is correct |
20 |
Correct |
6 ms |
6492 KB |
Output is correct |
21 |
Correct |
272 ms |
11512 KB |
Output is correct |
22 |
Correct |
256 ms |
11460 KB |
Output is correct |
23 |
Correct |
268 ms |
11416 KB |
Output is correct |
24 |
Correct |
267 ms |
11456 KB |
Output is correct |
25 |
Correct |
257 ms |
11504 KB |
Output is correct |
26 |
Correct |
295 ms |
11508 KB |
Output is correct |
27 |
Correct |
255 ms |
11424 KB |
Output is correct |
28 |
Correct |
308 ms |
11416 KB |
Output is correct |
29 |
Correct |
258 ms |
11112 KB |
Output is correct |
30 |
Correct |
447 ms |
11544 KB |
Output is correct |
31 |
Correct |
366 ms |
11572 KB |
Output is correct |
32 |
Correct |
392 ms |
11520 KB |
Output is correct |
33 |
Correct |
466 ms |
11476 KB |
Output is correct |
34 |
Correct |
411 ms |
11460 KB |
Output is correct |
35 |
Correct |
400 ms |
11640 KB |
Output is correct |
36 |
Correct |
441 ms |
11588 KB |
Output is correct |