ACMP 537
Перейти к навигации
Перейти к поиску
Ссылка на задачу
Комментарии
Вид подзадачи: 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).