|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 15-1. Шахматы
(Разбор)
Ответ задачи вычисляется по формуле N2*(N-1)2* ...*(N-K+1)2/K!. Действительно, первую ладью можно поставить в любую из N2 клеток - при этом она побьет 2*(N-1)+1 клеток. Соответственно, вторую ладью можно поставить N2-(2*(N-1)+1)= (N-1)2 способами. И так далее до K-й, которую можно поставить в любую из (N-K+1)2 еще не битых клеток. А поскольку порядок выставления ладей не существенен, то надо поделить полученное произведение на количество способов перенумеровать K ладей, т.е. K!.
В данной задаче ограничения подобраны так, что все вычисления не выходят за пределы стандартных целочисленных типов.