Чистый ранг
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Динамическое программирование
- Математика
Пусть S — множество целых чисел, каждое не меньше 2. Ранг числа x из S — его номер в S по возрастанию, считая с 1. Число x из S чистое относительно S, если цепочка «x, ранг x, ранг ранга x, …» всё время остаётся внутри S, пока не дойдёт до 1 (единица в S не входит). Например, при S = {2, 3, 5} число 5 чистое: ранг 5 равен 3, ранг 3 равен 2, ранг 2 равен 1.
Дано целое n (2 ≤ n ≤ 150). Посчитайте, сколько существует подмножеств S множества {2, 3, …, n}, для которых n входит в S и чистое относительно S. Верните ответ по модулю 100003.
Пример: 5 → 5 (подходят {5}, {2, 5}, {2, 3, 5}, {3, 4, 5} и {2, 3, 4, 5}).
Источник: Coding Competitions Archive, codejam/2010/round_1b/your_rank_is_pure · © Google LLC · Apache-2.0 · условие переведено и дополнено