|
||||||||||||||
МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике
Дистанционные семинары
по подготовке к олимпиадам по информатике
Задача 15-2. Карточки
(Разбор)
Обозначим длину исходного слова N. Мы можем переставить буквы этого слова N! способами. Однако, если в слове встречаются, например, две буквы "a", то их отностельный порядок нам не важен. Поэтому надо поделить ответ на 2!. Аналогично для каждой буквы надо вычислить, сколько раз она встречается в слове, и поделить ответ на факториал этого количества.
Например, для слова "babab" получим 5!/(2!*3!)=10 различных слов.
В ограничениях задачи вычисления не умещаются в 32-битный целый тип LongInt, поэтому надо использовать 64-битный тип (int64 в Pascal или long long в C), либо большой тип с плавающей точкой (double или extended).