https://acm.khpnets.info/w39/index.php?action=history&feed=atom&title=ACMP_537 2026-05-13T11:03:53Z История изменений этой страницы в вики MediaWiki 1.39.3 https://acm.khpnets.info/w39/index.php?title=ACMP_537&diff=1197&oldid=prev 2014-12-31T06:37:39Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="ru"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Предыдущая версия</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Версия от 06:37, 31 декабря 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l12">Строка 12:</td> <td colspan="2" class="diff-lineno">Строка 12:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Сборник задач: ACMP]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Сборник задач: ACMP]]</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Задачи: Динамическое программирование<del style="font-weight: bold; text-decoration: none;">: </del>подмножество, параметр]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Задачи: Динамическое программирование <ins style="font-weight: bold; text-decoration: none;">&amp;mdash; </ins>подмножество, параметр]]</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Задачи: Получение объекта по номеру]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category: Задачи: Получение объекта по номеру]]</div></td></tr> </table>

Ctrlalt https://acm.khpnets.info/w39/index.php?title=ACMP_537&diff=1195&oldid=prev 2014-12-31T06:33:42Z

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

Ctrlalt