You roll k fair dice, each with faces 1..sides, and keep the largest value. Write expected_max_of_dice(k: int, sides: int) -> Fraction that returns its exact expected value as a fractions.Fraction.
expected_max_of_dice(1, 6) # Fraction(7, 2) one die: 3.5
expected_max_of_dice(2, 6) # Fraction(161, 36) about 4.47
expected_max_of_dice(3, 1) # Fraction(1, 1) every die shows 1
Constraints: 1 <= k <= 200, 1 <= sides <= 2000.
Enumerating all sides^k outcomes is hopeless beyond tiny inputs; aim for about sides terms.
Show hint
"The maximum is at most m" means every die is at most m, which is easy to compute. From P(max ≤ m) you can get P(max = m) (or use E[X] = Σ_{m≥1} P(X ≥ m) for a non-negative integer X).