Пятеро друзей сложили шляпы в кучу, и каждый наугад берёт одну обратно. Сколькими способами может случиться так, что никому не достанется своя шляпа? Перестановка n элементов, в которой ни один элемент не остаётся на исходном месте, называется беспорядком. Количество беспорядков начинается с 1, 0, 1, 2, 9, 44 и подчиняется формуле D(n) = (n − 1) × (D(n − 1) + D(n − 2)).
Реализуйте derangements(n).
Входные данные
n: количество элементов.
Выходные данные
Верните количество беспорядков из n элементов. D(0) равно 1 (в пустой перестановке нет ничего, что могло бы остаться на месте), а D(1) равно 0.
Ограничения
0 ≤ n ≤ 20
Примеры
Ввод:
n = 3
Ожидаемый вывод:
expected = 2
Ввод:
long long n = 3;
Ожидаемый вывод:
long long expected = 2;
Ввод:
long n = 3;
Ожидаемый вывод:
long expected = 2;
Пояснение
Для элементов A, B, C все элементы сдвигают только BCA и CAB, поэтому ответ 2.
Ввод:
n = 4
Ожидаемый вывод:
expected = 9
Ввод:
long long n = 4;
Ожидаемый вывод:
long long expected = 9;
Ввод:
long n = 4;
Ожидаемый вывод:
long expected = 9;
Пояснение
D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Начните с D(0) = 1 и D(1) = 0.
Подсказка 2
Каждое следующее значение вычисляется из двух предыдущих и текущего n.
Подсказка 3
В каждый момент нужны только два последних значения.
Ожидаемая сложность
время O(n), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.