Submission #1986532
Source Code Expand
$N = <STDIN>+0; @P=split " ",<STDIN>; $m=1000000007; unshift @P,-1; for($i=1;$i<=$N;$i++) { push @{$IP[$P[$i]]},$i; } $lv{0}=0; for($i=0;$i<=$N;$i++) { $lv=$lv{$i}; $lvsum{$lv}+=1; for($j=0;$j<=$#{$IP[$i]};$j++) { $lv{$IP[$i][$j]}=$lv+1; } } for($i=$N;$i>=0;$i--) { $l=$IP[$i]; $mj=$#{$l}; if ($mj<0) { $A[$i][0]=1; $B[$i][0]=1; next; } if ($mj==0) { $di=${$l}[0]; $A[$i]=$A[$di]; $B[$i]=$B[$di]; } else { $md=-1; for($j=0;$j<=$mj;$j++) { $pdi=${$l}[$j]; if ($md < $#{$A[$pdi]}) { $di=$pdi; $md=$#{$A[$di]}; } } $A[$i]=$A[$di]; $B[$i]=$B[$di]; for($d=0;$d<=$md;$d++) { $A=$A[$i][$d]; $B=$B[$i][$d]; $D=0; for($j=0;$j<=$mj;$j++) { $ij=${$l}[$j]; next if ($di==$ij); next if ($A[$ij][$d]==0); $D=($A*$A[$ij][$d]+$D*($A[$ij][$d]+$B[$ij][$d]))%$m; $A=($A*$B[$ij][$d]+$B*$A[$ij][$d] )%$m; $B=($B*$B[$ij][$d] )%$m; } $A[$i][$d]=$A; $B[$i][$d]=($B+$D) % $m; } } unshift @{$A[$i]},1; unshift @{$B[$i]},1; } $pow[0]=1;for($p=0;$p<$N;$p++){ $pow[$p+1]=($pow[$p]*2) % $m; } $sum=0; for($d=0;$A[0][$d]>0;$d++) { $sum=($sum + $A[0][$d]*$pow[$N+1-$lvsum{$d}]) % $m; } print $sum,"\n";
Submission Info
Submission Time | |
---|---|
Task | E - Smuggling Marbles |
User | rei_atcoder |
Language | Perl (v5.18.2) |
Score | 1000 |
Code Size | 1270 Byte |
Status | AC |
Exec Time | 2540 ms |
Memory | 155264 KB |
Compile Error
./Main.pl syntax OK
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | 600 / 600 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s1_14.txt, s1_15.txt, s1_16.txt, s1_17.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s1_14.txt, s1_15.txt, s1_16.txt, s1_17.txt, s2_01.txt, s2_02.txt, s2_03.txt, s2_04.txt, s2_05.txt, s2_06.txt, s2_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt, s2_29.txt, s2_30.txt, s2_31.txt, s2_32.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 2 ms | 512 KB |
00_example_02.txt | AC | 2 ms | 512 KB |
00_example_03.txt | AC | 2 ms | 512 KB |
s1_01.txt | AC | 6 ms | 1024 KB |
s1_02.txt | AC | 6 ms | 896 KB |
s1_03.txt | AC | 9 ms | 1408 KB |
s1_04.txt | AC | 2 ms | 512 KB |
s1_05.txt | AC | 5 ms | 768 KB |
s1_06.txt | AC | 11 ms | 2048 KB |
s1_07.txt | AC | 4 ms | 896 KB |
s1_08.txt | AC | 10 ms | 1792 KB |
s1_09.txt | AC | 4 ms | 896 KB |
s1_10.txt | AC | 14 ms | 1920 KB |
s1_11.txt | AC | 5 ms | 896 KB |
s1_12.txt | AC | 10 ms | 1280 KB |
s1_13.txt | AC | 2 ms | 512 KB |
s1_14.txt | AC | 14 ms | 1920 KB |
s1_15.txt | AC | 16 ms | 1792 KB |
s1_16.txt | AC | 13 ms | 1920 KB |
s1_17.txt | AC | 15 ms | 1920 KB |
s2_01.txt | AC | 115 ms | 12160 KB |
s2_02.txt | AC | 25 ms | 2688 KB |
s2_03.txt | AC | 838 ms | 91392 KB |
s2_04.txt | AC | 552 ms | 53760 KB |
s2_05.txt | AC | 991 ms | 90624 KB |
s2_06.txt | AC | 1286 ms | 133376 KB |
s2_07.txt | AC | 828 ms | 77952 KB |
s2_08.txt | AC | 417 ms | 37760 KB |
s2_09.txt | AC | 1203 ms | 130560 KB |
s2_10.txt | AC | 991 ms | 96640 KB |
s2_11.txt | AC | 1022 ms | 155264 KB |
s2_12.txt | AC | 17 ms | 2944 KB |
s2_13.txt | AC | 901 ms | 135936 KB |
s2_14.txt | AC | 900 ms | 135936 KB |
s2_15.txt | AC | 810 ms | 122880 KB |
s2_16.txt | AC | 105 ms | 12288 KB |
s2_17.txt | AC | 22 ms | 2688 KB |
s2_18.txt | AC | 875 ms | 87936 KB |
s2_19.txt | AC | 489 ms | 53760 KB |
s2_20.txt | AC | 1489 ms | 137856 KB |
s2_21.txt | AC | 1636 ms | 135296 KB |
s2_22.txt | AC | 1393 ms | 143232 KB |
s2_23.txt | AC | 1505 ms | 137728 KB |
s2_24.txt | AC | 2246 ms | 128640 KB |
s2_25.txt | AC | 2540 ms | 125440 KB |
s2_26.txt | AC | 2494 ms | 125696 KB |
s2_27.txt | AC | 2282 ms | 131072 KB |
s2_28.txt | AC | 2185 ms | 130816 KB |
s2_29.txt | AC | 941 ms | 136192 KB |
s2_30.txt | AC | 944 ms | 136192 KB |
s2_31.txt | AC | 1108 ms | 130688 KB |
s2_32.txt | AC | 1081 ms | 130688 KB |