https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=ACMP_512 2026-06-02T22:10:27Z История изменений этой страницы в вики MediaWiki 1.39.3 https://acm.khpnets.info/w39/index.php?title=ACMP_512&diff=1392&oldid=prev 2015-02-06T14:13:09Z

<p>Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&amp;id_task=512 ACMP #512 — Выпускной] == Комментарии == Вид подз…»</p> <p><b>Новая страница</b></p><div>== Ссылка на задачу ==<br /> * [http://acmp.ru/?main=task&amp;id_task=512 ACMP #512 &amp;mdash; Выпускной]<br /> <br /> == Комментарии ==<br /> Вид подзадачи: d[i][mask][p] &amp;mdash; число способов сформировать p пар из первых i мальчиков и подмножества девочек, заданного маской mask. <br /> <br /> Рекуррентная формула: d[i][mask][p] = d[i - 1][mask][p] + &amp;sum;d[i - 1][pMask][p - 1], где pMask &amp;mdash; все маски, получаемые из mask выключением битов, соответствующих девочкам, с которыми может быть в паре (i - 1)-й мальчик.<br /> <br /> База рекурсии: d[0][mask][0] = 1.<br /> <br /> Вид ответа: d[n][2&lt;sup&gt;m&lt;/sup&gt; - 1][k]. Сложность O(N&lt;sup&gt;3&lt;/sup&gt; &amp;times; 2&lt;sup&gt;N&lt;/sup&gt;).<br /> <br /> [[Category: Сборник задач: ACMP]]<br /> [[Category: Задачи: Динамическое программирование &amp;mdash; подмножество, два параметра]]</div>

Ctrlalt