Числа беспорядков (derangements): сколько перестановок без неподвижных точек?
Задача про "никто не получил свой подарок": сколько перестановок из n элементов, где ни один элемент не стоит на своём месте? Это число беспорядков D_n. Как его вывести и как посчитать по модулю для n до 10^6?
2 ответа
Число беспорядков (субфакториал) D_n удобнее всего считать по рекуррентте:
D_n = (n − 1) · (D_{n−1} + D_{n−2}), D_0 = 1, D_1 = 0.
Идея вывода: первый элемент идёт на одну из (n−1) чужих позиций j. Дальше либо j «возвращает» элемент 1 на позицию первого (тогда остаётся беспорядок из n−2 элементов, D_{n−2}), либо нет — тогда это как беспорядок из n−1 элементов с переименованием (D_{n−1}). Отсюда множитель (n−1).
const int MOD = 1e9 + 7;
vector<long long> derangements(int n) {
vector<long long> D(n + 1);
D[0] = 1;
if (n >= 1) D[1] = 0;
for (int i = 2; i <= n; i++)
D[i] = (long long)(i - 1) % MOD * ((D[i-1] + D[i-2]) % MOD) % MOD;
return D;
}
Сложность O(n) по времени и памяти. Есть и формула через включение-исключение: D_n = n! · Σ_{j=0}^{n} (−1)^j / j!, откуда D_n ≈ n!/e. Но рекуррента кодируется проще и не требует обратных факториалов.
Если нужно «ровно k неподвижных точек», ответ = C(n, k) · D_{n−k}: выбираем k фиксированных и делаем беспорядок на остальных. Это частый подвопрос на олимпиадах. И не путай: вероятность того, что случайная перестановка — беспорядок, стремится к 1/e ≈ 0.3679 при росте n, что иногда удивляет в задачах на вероятность.