Submission #1986497

---

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;
}
for($i=$N;$i>=0;$i--) {
	$l=$IP[$i];
	$mj=$#{$l};
	$md=-1;
	for($j=0;$j<=$mj;$j++) {
		$pdi=${$l}[$j];
		if ($md < $#{$A[$pdi]}) { $di=$pdi; $md=$#{$A[$di]}; }
	}
	if ($md<0) {
		$A[$i][0]=1;
		$B[$i][0]=1;
		$C[$i][0]=1;
		next;
	}
	$A[$i]=$A[$di];
	$B[$i]=$B[$di];
	$C[$i]=$C[$di];
	
	for($d=0;$d<=$md;$d++) {
		$A=$A[$i][$d];
		$B=$B[$i][$d];
		$C=$C[$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;
			$C=$C+$C[$ij][$d];
		}
		$A[$i][$d]=$A;
		$B[$i][$d]=($B+$D) % $m;
		$C[$i][$d]=$C;
	}
	unshift @{$A[$i]},1;
	unshift @{$B[$i]},1;
	unshift @{$C[$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-$C[0][$d]]) % $m;
}
print $sum,"\n";

Submission Info

Compile Error

./Main.pl syntax OK

Judge Result