ACMP 617

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

• 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] = C^k_{(h × v)} - Σ(d[k][h' < h][v' < v] × C^h'_h × C^v'_v). (От общего числа способов расположить k ладей на h горизонталях и v вертикалях отнимаем число способов выбрать меньшее количество горизонталей и вертикалей и расположить k ладей на них)

Ответ на задачу — Σ((d[a][ha][va] × C^ha_n × C^va_m) × (d[b][hb][vb] × C^hb_{(n - ha)} × C^vb_{(m - va)})). (Число способов выбрать на доске n × m ha горизонталей и va вертикалей и расставить в них a ладей × число способов выбрать на оставшейся части доски hb горизонталей и vb вертикалей и расставить в них b ладей)