Ссылка на задачу с LeetCode — 2338. Count the Number of Ideal Arrays.
📋 Описание задачи
Дан массив длины n, состоящий из целых чисел от 1 до maxValue. Массив называется «идеальным», если:
- Каждый элемент принадлежит диапазону
[1, maxValue]
- Каждый следующий элемент делится на предыдущий
Нужно посчитать количество различных идеальных массивов длины n.
Ответ вернуть по модулю 10⁹ + 7.
💬 Пример
- Вход:
n = 2, maxValue = 5
- Выход:
10
- Пояснение: Возможные идеальные массивы:
- Начинаются с
1 (5 массивов): [1,1], [1,2], [1,3], [1,4], [1,5]
- Начинаются с
2 (2 массива): [2,2], [2,4]
- Начинаются с
3 (1 массив): [3,3]
- Начинаются с
4 (1 массив): [4,4]
- Начинаются с
5 (1 массив): [5,5]
- Всего:
5 + 2 + 1 + 1 + 1 = 10 идеальных массивов.
💡 Идея
- Любую цепочку
i₀ → i₁ → ... → iₙ можно поделить на i₀, сведя задачу к подсчёту цепочек, начинающихся с единицы:
Читать дальше →