Все задачи
Средне Решено: 0 Процент решений: 0%

Беспорядки (перестановки без неподвижных точек)

Посчитайте перестановки n элементов, в которых ни один элемент не остаётся на своём месте.

Чему вы научитесь

  • Превращать комбинаторное рассуждение в рекуррентное соотношение
  • Вычислять рекуррентное соотношение, начиная с базовых случаев
  • Обрабатывать случаи n = 0 и n = 1

Условие

Пятеро друзей сложили шляпы в кучу, и каждый наугад берёт одну обратно. Сколькими способами может случиться так, что никому не достанется своя шляпа? Перестановка 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

Примеры

Пример 1
Ввод:
n = 3

Ожидаемый вывод:
expected = 2
Ввод:
long long n = 3;

Ожидаемый вывод:
long long expected = 2;
Ввод:
long n = 3;

Ожидаемый вывод:
long expected = 2;

Пояснение

Для элементов A, B, C все элементы сдвигают только BCA и CAB, поэтому ответ 2.

Пример 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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.