ACMP 512
Перейти к навигации
Перейти к поиску
Ссылка на задачу
Комментарии
Вид подзадачи: d[i][mask][p] — число способов сформировать p пар из первых i мальчиков и подмножества девочек, заданного маской mask.
Рекуррентная формула: d[i][mask][p] = d[i - 1][mask][p] + ∑d[i - 1][pMask][p - 1], где pMask — все маски, получаемые из mask выключением битов, соответствующих девочкам, с которыми может быть в паре (i - 1)-й мальчик.
База рекурсии: d[0][mask][0] = 1.
Вид ответа: d[n][2m - 1][k]. Сложность O(N3 × 2N).