ACMP 537: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=537 ACMP #537 — Перестановки — 3] == Комментарии == …») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 12: | Строка 12: | ||
[[Category: Сборник задач: ACMP]] | [[Category: Сборник задач: ACMP]] | ||
[[Category: Задачи: Динамическое программирование | [[Category: Задачи: Динамическое программирование — подмножество, параметр]] | ||
[[Category: Задачи: Получение объекта по номеру]] | [[Category: Задачи: Получение объекта по номеру]] | ||
Текущая версия от 06:37, 31 декабря 2014
Ссылка на задачу
Комментарии
Вид подзадачи: d[mask][i] — количество k-перестановок подмножества, заданного маской mask, первый элемент которых имеет индекс i.
Рекуррентная формула: d[mask][i] = ∑(d[mask'][j]), где mask' = (mask & ~(1 << i)), j ∈ mask' и gcd(a[i], a[j]) >= k.
База рекурсии: d[2i][i] = 1; если i ∉ mask, то d[mask][i] = 0.
Ответ восстанавливается последовательно стандартным способом отыскания объекта по номеру. Сложность O(N × 2N).