ACMP 617

Материал из Олимпиадное программирование в УлГТУ
Версия от 01:57, 6 января 2016; Ctrlalt (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

Похожие задачи

Комментарии

Пусть 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 ладей)