#include<bits/stdc++.h>
using namespace std;
const int maxn=605,tmaxn=1205;
int mod=1e9+7;
long long mypow(long long m,long long y){
if(y==0){
return 1;
}
long long p=mypow(m,(y>>1));
p*=p;
p%=mod;
if(y&1){
p*=m;
p%=mod;
}
return p;
}
int fact[tmaxn],revfact[tmaxn],magemishe[tmaxn],res[tmaxn][tmaxn],dp[tmaxn],n;
int vas[tmaxn];
int ww(int a){
if(a>=mod){
a-=mod;
}
return a;
}
void aval(){
fact[0]=1;
for(int i=1;i<tmaxn;i++){
fact[i]=1ll*fact[i-1]*i%mod;
}
revfact[tmaxn-1]=mypow(fact[tmaxn-1],mod-2);
for(int i=tmaxn-2;i>=0;i--){
revfact[i]=1ll*revfact[i+1]*(i+1)%mod;
}
}
int c(int i,int j){
if(i<0||j<0||j>i){
return 0;
}
int ret=1ll*fact[i]*revfact[j]%mod*revfact[i-j]%mod;
return ret;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
aval();
cin>>n;
for(int i=0;i<n;i++){
int d;
cin>>d;
vas[d]=1;
}
dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i]+=1ll*c(i-1,j-1)*(i-j+2)%mod*dp[i-j]%mod*dp[j-1]%mod;
dp[i]=ww(dp[i]);
}
}
res[n*2+1][0]=1;
int oomade=0,naumade=0;
for(int i=n*2;i>=1;i--){
if(vas[i]){
for(int j=0;j<=oomade+1;j++){
res[i][j]=res[i+1][j];
for(int h=1;h<=j;h++){
res[i][j]+=1ll*res[i+1][h-1]*dp[j-h]%mod*c(oomade-h+1,j-h)%mod*(j-h+2)%mod;
res[i][j]=ww(res[i][j]);
}
}
oomade++;
}
else{
for(int j=0;j<=oomade;j++){
res[i][j]=1ll*res[i+1][j]*max(j-naumade,0)%mod;
}
naumade++;
}
}
int mainres=1ll*res[1][n]*mypow(mypow(2,n),mod-2)%mod;
cout<<mainres<<"\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
2 ms |
852 KB |
Output is correct |
| 12 |
Correct |
2 ms |
724 KB |
Output is correct |
| 13 |
Correct |
2 ms |
852 KB |
Output is correct |
| 14 |
Correct |
2 ms |
852 KB |
Output is correct |
| 15 |
Correct |
2 ms |
852 KB |
Output is correct |
| 16 |
Correct |
2 ms |
728 KB |
Output is correct |
| 17 |
Correct |
2 ms |
724 KB |
Output is correct |
| 18 |
Correct |
2 ms |
852 KB |
Output is correct |
| 19 |
Correct |
2 ms |
852 KB |
Output is correct |
| 20 |
Correct |
2 ms |
852 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
2 ms |
852 KB |
Output is correct |
| 12 |
Correct |
2 ms |
724 KB |
Output is correct |
| 13 |
Correct |
2 ms |
852 KB |
Output is correct |
| 14 |
Correct |
2 ms |
852 KB |
Output is correct |
| 15 |
Correct |
2 ms |
852 KB |
Output is correct |
| 16 |
Correct |
2 ms |
728 KB |
Output is correct |
| 17 |
Correct |
2 ms |
724 KB |
Output is correct |
| 18 |
Correct |
2 ms |
852 KB |
Output is correct |
| 19 |
Correct |
2 ms |
852 KB |
Output is correct |
| 20 |
Correct |
2 ms |
852 KB |
Output is correct |
| 21 |
Correct |
1083 ms |
5840 KB |
Output is correct |
| 22 |
Correct |
1076 ms |
5840 KB |
Output is correct |
| 23 |
Correct |
1079 ms |
5768 KB |
Output is correct |
| 24 |
Correct |
1079 ms |
5864 KB |
Output is correct |
| 25 |
Correct |
1080 ms |
5828 KB |
Output is correct |
| 26 |
Correct |
1082 ms |
5824 KB |
Output is correct |
| 27 |
Correct |
1079 ms |
5760 KB |
Output is correct |
| 28 |
Correct |
1077 ms |
5868 KB |
Output is correct |
| 29 |
Correct |
1080 ms |
5516 KB |
Output is correct |
| 30 |
Correct |
1395 ms |
5940 KB |
Output is correct |
| 31 |
Correct |
1239 ms |
5892 KB |
Output is correct |
| 32 |
Correct |
1310 ms |
5908 KB |
Output is correct |
| 33 |
Correct |
1368 ms |
5836 KB |
Output is correct |
| 34 |
Correct |
1235 ms |
5852 KB |
Output is correct |
| 35 |
Correct |
1312 ms |
5904 KB |
Output is correct |
| 36 |
Correct |
1371 ms |
6060 KB |
Output is correct |
