Hello Codeforces!

Combinatorics and counting problems are a staple in competitive programming. Today, I want to discuss a classic yet incredibly powerful concept that frequently appears in $$$O(N)$$$ DP optimizations and math-heavy problems: Derangements.

Whether you are grinding Div. 2 B/C problems or tackling high-level combinatorics on USACO and AtCoder, understanding the intuition behind derangements is a massive advantage. Let's dive in!

1. What is a Derangement?

A derangement is a permutation of the elements of a set such that no element appears in its original position.

If we have an array $$$A = [1, 2, 3, \dots, N]$$$, a derangement is a permutation $$$P$$$ where $$$P[i] \neq i$$$ for all $$$1 \le i \le N$$$.

Classic Examples: * Secret Santa: $$$N$$$ people put their names in a hat and each draws one. A valid state is when nobody draws their own name. * The Hat-Check Problem: $$$N$$$ guests check their hats. The attendant hands them back randomly. What is the probability nobody gets their own hat?

The number of derangements of a set of size $$$N$$$ is denoted as $$$!N$$$ (read as subfactorial $$$N$$$) or $$$D_n$$$.

2. The Core Mathematics & Recurrences

To solve this efficiently, we don't generate permutations. Instead, we rely on recurrence relations.

Recurrence 1: The Intuitive Approach

The most standard recurrence for derangements is:

Proof / Intuition: Imagine $$$N$$$ people. Let person $$$1$$$ take the spot of person $$$i$$$ ($$$2 \le i \le n$$$). There are exactly $$$(n - 1)$$$ choices for $$$i$$$. Now, what does person $$$i$$$ do? 1. Case 1 (They swap): Person $$$i$$$ takes person $$$1$$$'s original spot. The two people have perfectly swapped. The remaining $$$(n - 2)$$$ people must now be deranged among themselves. This gives $$$D_{n-2}$$$ ways. 2. Case 2 (They don't swap): Person $$$i$$$ does not take person $$$1$$$'s spot. This is mathematically identical to saying person $$$i$$$ is forbidden from exactly one specific spot (spot 1), while the other $$$(n-2)$$$ people are forbidden from their own spots. This maps perfectly to a derangement problem of size $$$(n - 1)$$$. This gives $$$D_{n-1}$$$ ways.

Summing these cases and multiplying by the $$$(n - 1)$$$ choices yields our formula!

Recurrence 2: The Linear Step

A tighter recurrence relation exists, which is incredibly useful for space optimization:

The Closed Form (Inclusion-Exclusion)

Using the Principle of Inclusion-Exclusion (PIE), the exact formula is:

(Fun fact: As $$$n \to \infty$$$, the probability of a random permutation being a derangement approaches $$$\frac{1}{e} \approx 36.78\%$$$.)

3. Implementation (C++)

In CP, we usually need to compute $$$D_n \pmod M$$$ (where $$$M = 10^9+7$$$ or $$$998244353$$$).

Approach A: $$$O(N)$$$ Precomputation

Perfect when you need to answer multiple test cases. Space Complexity: $$$O(N)$$$. Time Complexity: $$$O(N)$$$.

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1e6;

vector<long long> D(MAXN + 1);

void precompute() {
    D[0] = 1; // Base case: 1 way to derange 0 elements
    D[1] = 0; // Base case: 0 ways to derange 1 element
    
    for (int i = 2; i <= MAXN; ++i) {
        D[i] = (i - 1) * (D[i - 1] + D[i - 2]) % MOD;
    }
}

void solve() {
    int n;
    cin >> n;
    cout << D[n] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Approach B: $$$O(1)$$$ Space Optimization

If you only need to query $$$D_n$$$ once for a massive $$$N$$$, you can roll the variables just like the Fibonacci sequence. Space Complexity: $$$O(1)$$$.

long long get_derangement(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    
    long long prev2 = 1; // D[0]
    long long prev1 = 0; // D[1]
    long long current = 0;
    
    for (int i = 2; i <= n; ++i) {
        current = (i - 1) * (prev1 + prev2) % MOD;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
}

4. Advanced Variations (For Div 1 / Hard Div 2)

Partial Derangements (Rencontres Numbers): What if a problem asks: "How many permutations exist where exactly $$$K$$$ elements are in their original positions?"

You choose which $$$K$$$ elements stay in place, and then completely derange the remaining $$$N - K$$$ elements:

Massive $$$N$$$ Queries using NTT: If $$$N \ge 10^5$$$ and the modulus allows, you can view the closed-form PIE formula as a convolution of two polynomials: $$$A[i] = \frac{(-1)^i}{i!}$$$ and $$$B[j] = j!$$$. This allows computing the entire array using Number Theoretic Transform (NTT) in $$$O(N \log N)$$$ time, though standard $$$O(N)$$$ is almost always sufficient unless there's a strict time limit on array generation.

5. Practice Problems

• CSES Task 1717 — Christmas Party
• Codeforces 1530D — Secret Santa
• Codeforces 340E — Iahub and Permutations

I hope this guide helps solidify your understanding of derangements! Feel free to ask questions in the comments or point out any other interesting problems that use this concept.

Happy coding!