ACMP 617
(перенаправлено с «Интернет-олимпиада 25.02.2006, усложнённый уровень, F»)
Перейти к навигации
Перейти к поиску
Ссылка на задачу
Похожие задачи
Комментарии
Пусть 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 ладей)