Задача g6_1045: День рождения Иванова (первоисточник неизвестен)
Иван Иванович Иванов пригласил на свой день рождения много гостей. Он написал на карточках фамилии всех гостей и разложил эти карточки на столе, полагая, что каждый гость сядет там, где обнаружит карточку со своей фамилией. Однако гости не обратили внимания на карточки и сели за стол в произвольном порядке. При этом Иван Иванович с удивлением обнаружил, что ни один гость не сел на предназначенное ему место, и задумался: а сколькими способами можно рассадить гостей так, чтобы ни один из них не сидел там, где лежала карточка с его фамилией? Помогите Ивану Ивановичу вычислить это число.
Считайте, что число гостей не превосходит 100 человек.
Входной файл: число гостей
Выходной файл: число способов
Решение g6_1045:
Гости Иванова могут сесть за стол N! способами. Несложно доказать, что число способов расположения гостей равно количеству перестановок N элементов. При этом мы также знаем, что одна из этих перестановок не является решением, т.к. гости точно не сели правильно. Как находить факториал мы знаем из задачи 1025 - Домино. Там тоже придется воспользоваться длинной арифметикой, т.к. по моим расчетам на пальцах факториал 100 не влезает в longint. Вычитание 1 из массива сделать несложно, почти также как сложение (открыть algolist - длинные числа, также можно посмотреть задачу 1021 - 2^n).