ACMP 512

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

• 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][2^m - 1][k]. Сложность O(N³ × 2^N).