|
Да никакой особой формулы нет. Простые наблюдения. Максимальное число всегда будет иметь вид ААА...АВВВ...В, где В = А+1, потому что стремимся увеличить старшие разряды (которые слева). Аналогично, минимальное 111...1А999...9, здесь уменьшаем старшие разряды. Ты и сам можешь поэкспериментировать с числами и заметить это.
Для подсчета количества не требуется бежать циклом от минимального числа к максимальному и каждое проверять на соответствие условиям. Суммируем количества вариантов для всех значений старшего разряда. Если старший разряд равен f, то за ним стоит calc(f, n - f, k - 1) вариантов - потому что справа от него (k - 1) цифр, сумма которых равна (n - f), а в старшем разряде цифра не менее чем f. Ну и оптимизация в виде Map, потому что по факту будет много повторных расчетов, и ускорение от оптимизации весьма ощутимое.
|