ACMP 537: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=537 ACMP #537 — Перестановки — 3] == Комментарии == …») |
(нет различий)
|
Версия от 06:33, 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).