ACMP 617: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=617 ACMP #617 — Ладьи] == Похожие задачи == * Интерне…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 14: | Строка 14: | ||
[[Category: Сборник задач: ACMP]] | [[Category: Сборник задач: ACMP]] | ||
[[Category: Задачи: Комбинаторика]] | [[Category: Задачи: Комбинаторика]] | ||
[[Category | [[Category: Задачи: Динамическое программирование — три параметра]] | ||
[[Category: Задачи: Длинная арифметика]] | [[Category: Задачи: Длинная арифметика]] | ||
Текущая версия от 01:57, 6 января 2016
Ссылка на задачу
Похожие задачи
Комментарии
Пусть d[k][h][v] — число способов расположить k ладей на ровно h горизонталях и v вертикалях.
Если k > h × v, то d[k][h][v] = 0, иначе d[k][h][v] = Ck(h × v) - Σ(d[k][h' < h][v' < v] × Ch'h × Cv'v). (От общего числа способов расположить k ладей на h горизонталях и v вертикалях отнимаем число способов выбрать меньшее количество горизонталей и вертикалей и расположить k ладей на них)
Ответ на задачу — Σ((d[a][ha][va] × Chan × Cvam) × (d[b][hb][vb] × Chb(n - ha) × Cvb(m - va))). (Число способов выбрать на доске n × m ha горизонталей и va вертикалей и расставить в них a ладей × число способов выбрать на оставшейся части доски hb горизонталей и vb вертикалей и расставить в них b ладей)