| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 227662 |
2020-04-28T10:34:17 Z |
imsifile |
Ruins 3 (JOI20_ruins3) |
C++ |
|
913 ms |
3768 KB |
#include<stdio.h>
typedef long long lld;
const lld mod=1000000007;
int N, chk[1212], pos[666], neg[666], xs[666];
lld dy[666][666], pw[1212], fac[1212], rfac[1212], rgop[1212], all[666], sums[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; }
}
xs[N]=N;
for(int i=0; i<N; i++) xs[i]=(neg[i]-1+chk[neg[i]-1])/2;
for(int i=N; i>=0; i--){
for(int k=i+1; k<=N; k++) sums[k]=0;
for(int j=i; j>=0; j--){
for(int k=i+1; k<=N; k++){
sums[k]+=dy[k][j]*all[k-i]%mod*perm(xs[j]-i,k-i)%mod*rfac[i-j]%mod;
sums[k]%=mod;
}
if(i==N && j==N) dy[i][j]=1;
else if(i==xs[j]) dy[i][j]=dy[i][j+1]*chk[neg[j]-1]%mod;
else if(i>xs[j]) dy[i][j]=0;
else {
for(int k=i+1; k<=N; k++) dy[i][j]+=sums[k]*fac[i-j]%mod;
dy[i][j]%=mod;
}
for(int k=i+1; k<=N; k++){
sums[k]+=dy[k][j]*all[k-i]%mod*(mod-perm(xs[j-1]-i,k-i))%mod*rfac[i-j]%mod;
sums[k]%=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 |
4 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 |
5 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 |
4 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 |
5 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 |
4 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 |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
6 ms |
640 KB |
Output is correct |
| 19 |
Correct |
5 ms |
640 KB |
Output is correct |
| 20 |
Correct |
5 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 |
4 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 |
5 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 |
4 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 |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
6 ms |
640 KB |
Output is correct |
| 19 |
Correct |
5 ms |
640 KB |
Output is correct |
| 20 |
Correct |
5 ms |
640 KB |
Output is correct |
| 21 |
Correct |
441 ms |
3428 KB |
Output is correct |
| 22 |
Correct |
451 ms |
3456 KB |
Output is correct |
| 23 |
Correct |
421 ms |
3452 KB |
Output is correct |
| 24 |
Correct |
448 ms |
3448 KB |
Output is correct |
| 25 |
Correct |
5 ms |
384 KB |
Output is correct |
| 26 |
Correct |
5 ms |
384 KB |
Output is correct |
| 27 |
Correct |
5 ms |
384 KB |
Output is correct |
| 28 |
Correct |
417 ms |
3448 KB |
Output is correct |
| 29 |
Correct |
5 ms |
384 KB |
Output is correct |
| 30 |
Correct |
913 ms |
3448 KB |
Output is correct |
| 31 |
Correct |
674 ms |
3448 KB |
Output is correct |
| 32 |
Correct |
813 ms |
3584 KB |
Output is correct |
| 33 |
Correct |
862 ms |
3428 KB |
Output is correct |
| 34 |
Correct |
684 ms |
3768 KB |
Output is correct |
| 35 |
Correct |
787 ms |
3576 KB |
Output is correct |
| 36 |
Correct |
889 ms |
3704 KB |
Output is correct |
