prob612-shlomif.p6
Source code: prob612-shlomif.p6
my @FACTS = (1); for 1 .. 100 -> $n { @FACTS.push(@FACTS[*-1] * $n); } say @FACTS[10]; sub nCr($n, @k_s) { return @FACTS[$n] / [*] @FACTS[|@k_s, $n-@k_s.sum]; } sub calc_count($l, $w_zero, $num_nat_digits) { my $num_digits = $num_nat_digits + ($w_zero ?? 1 !! 0); if $num_digits > $l { return 0; } if $w_zero { my $ret = 0; # Choose a pivot for the first place and go for it for 0 .. $l-2 -> $cnt { $ret += nCr($l-1, [$cnt]) * calc_count($l - 1 - $cnt, False, $num_nat_digits); } return $ret * $num_nat_digits; } sub rec(@counts, $sum) { if $sum > $l { return 0; } if @counts == $num_digits { if $sum != $l { return 0; } return nCr($l, @counts) * nCr($num_digits,(bag @counts).values); } my $ret = 0; for 1 .. (+@counts ?? @counts[*-1] !! $l - $num_digits + 1) -> $nxt { $ret += rec([|@counts, $nxt], $sum + $nxt); } return $ret; } return rec([], 0); } sub solve($myl) { my @counts; for [False, True] -> $z { for 0 .. 9 -> $n { my $v = sum(map { calc_count($_, $z, $n) }, 0 .. $myl); if $v > 0 { @counts.push([$z, $n, $v]); } } } say(@counts); my $ret = 0; for 0 ..^@counts -> $i { my ($zi, $ni, $vi) = |@counts[$i]; for $i ..^@counts -> $j { my ($zj, $nj, $vj) = |@counts[$j]; for 0 .. min($ni, $nj) -> $num_common { if ($num_common == 0 and (!$zi or !$zj)) { next; } my $i_num_diff = $ni - $num_common; my $j_num_diff = $nj - $num_common; if $num_common + $i_num_diff + $j_num_diff > 9 { next; } my $result = $vi * $vj * nCr(9, [$num_common, $i_num_diff, $j_num_diff]); if $i == $j { if $num_common == $ni { $result -= $vi * nCr(9, [$ni]) } } else { $result *= 2; } say ("num_common=", $num_common, "i=", $i, "j=", $j, "r=", $result); $ret += $result; } } } return $ret +> 1; } say ("s[fast] = ", solve(2)); my $my_solution = solve(18); printf("solution = %d ( MOD = %d )\n", $my_solution, $my_solution % 1000267129); =finish