ACMP 673

Ссылка на задачу

• ACMP #673 — N-значные числа — 2

Комментарии

Вид подзадачи: d[k][s][p] — количество k-значных чисел с суммой цифр s и произведением цифр p.

Рекуррентная формула: d[k][s][p] = ∑d[k - 1][s - i][p / i], где i ∈ 1..9 и p делится на i. Целесообразно использовать просмотр вперёд: d[k][s][p] добавляется к d[k + 1][s + i][p * i], где i ∈ 1..9.

База рекурсии: d[1][i][i] = 1, где i ∈ 0..9.

Вид ответа: ∑d[n][i][i], где i ∈ 0..(9 × n). Сложность O(N³).

Вычисление минимального числа производится аналогичной динамикой.