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
AC × 3
AC × 20
AC × 52
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