ACMP 537

Материал из Олимпиадное программирование в УлГТУ
Версия от 06:33, 31 декабря 2014; Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=537 ACMP #537 — Перестановки — 3] == Комментарии == …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

Комментарии

Вид подзадачи: 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).