Подсчёт чисел в диапазоне с определённой суммой цифр

Условие

В программу передаётся неотрицательное целое значение s. Требуется написать программу, которая определит количество целых чисел в диапазоне от 0 (включительно) до 10^12 (не включая верхнюю границу), у которых сумма цифр равна s.

Формат входных данных На вход подаётся целое неотрицательное число s (0 ≤ s ≤ 110).

Пример 1: Ввод: 0 Вывод: 1

Пример 2: Ввод: 1 Вывод: 12

Пример 3: Ввод: 12 Вывод: 31824

Ответ

Представьте каждое число как 12 цифр с ведущими нулями и примените динамику по позиции и сумме. Максимальная сумма — 108. Пример для s=12 ошибочен: правильный результат 1351142, не 31824.

dp[t] — число префиксов с суммой t:

def count_numbers(s):
    if not 0 <= s <= 108:
        return 0
    dp = [0] * (s + 1)
    dp[0] = 1
    for _ in range(12):
        next_dp = [0] * (s + 1)
        for total, count in enumerate(dp):
            for digit in range(10):
                if total + digit <= s:
                    next_dp[total + digit] += count
        dp = next_dp
    return dp[s]

Ведущие нули дают однозначное представление всех чисел от 0 до 10¹²−1. Для s=0 ответ 1, для s=1 — 12; 109 и 110 недостижимы. Сложность O(12·10·s).