#include<stdio.h>
typedef long long lld;
const lld mod=1000000007;
int N, chk[1212], pos[666], neg[666];
lld dy[666][666], pw[666], fac[1212], rfac[1212], rgop[1212], all[666];
int cc[666], ba[666], tmp[666], rcn[666];
lld rev(lld a){
lld g=1;
for(int r=mod-2; r; r>>=1){
if(r&1) g=g*a%mod;
a=a*a%mod;
}
return g;
}
lld perm(lld a, lld b){
if(a<b) return 0;
return fac[a]*rfac[a-b]%mod;
}
int main(){
scanf("%d", &N);
for(int i=1; i<=2*N; i++) chk[i]=1;
pw[0]=fac[0]=rfac[0]=1;
for(int i=1; i<=2*N; i++){
pw[i]=pw[i-1]*((mod+1)/2)%mod;
fac[i]=fac[i-1]*i%mod;
rfac[i]=rev(fac[i]);
rgop[i]=rev(4*i-2);
}
for(int i=1; i<=N; i++){
if(i==1) all[i]=1;
else all[i]=fac[2*i]*pw[i]%mod*rgop[i]%mod*rfac[i]%mod*rfac[i]%mod;
}
for(int i=0; i<N; i++){
scanf("%d", &neg[i]);
chk[neg[i]]=-1;
}
for(int i=1, pcn=0; i<=2*N; i++){
if(chk[i]>0) pos[pcn++]=i;
chk[i]+=chk[i-1];
if(chk[i]<0){ puts("0"); return 0; }
}
for(int i=N; i>=0; i--){
for(int j=i; j>=0; j--){
if(i==N && j==N) dy[i][j]=1;
else if(i==N || pos[i]>neg[j]) dy[i][j]=dy[i][j+1]*chk[neg[j]-1]%mod;
else {
for(int must=0; must<=i-j; must++){
int x=chk[neg[j+must]-1]+j+must-i, y=0;
if(must) y=chk[neg[j+must-1]-1]+j+must-1-i;
if(x==y) continue;
for(int k=1; k<=x; k++){
lld pm=(perm(x,k)-perm(y,k)+mod)*perm(i-j,must)%mod;
dy[i][j]+=dy[i+k][j+must]*all[k]%mod*pm%mod;
}
}
dy[i][j]%=mod;
}
}
}
printf("%lld\n", dy[0][0]);
return 0;
}
Compilation message
ruins3.cpp: In function 'int main()':
ruins3.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
ruins3.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &neg[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
640 KB |
Output is correct |
| 12 |
Correct |
5 ms |
640 KB |
Output is correct |
| 13 |
Correct |
5 ms |
640 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
640 KB |
Output is correct |
| 17 |
Correct |
4 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
640 KB |
Output is correct |
| 19 |
Correct |
7 ms |
640 KB |
Output is correct |
| 20 |
Correct |
7 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
384 KB |
Output is correct |
| 6 |
Correct |
4 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
4 ms |
384 KB |
Output is correct |
| 10 |
Correct |
4 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
640 KB |
Output is correct |
| 12 |
Correct |
5 ms |
640 KB |
Output is correct |
| 13 |
Correct |
5 ms |
640 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
640 KB |
Output is correct |
| 17 |
Correct |
4 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
640 KB |
Output is correct |
| 19 |
Correct |
7 ms |
640 KB |
Output is correct |
| 20 |
Correct |
7 ms |
640 KB |
Output is correct |
| 21 |
Incorrect |
28 ms |
3392 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
