错排问题详解：从递推公式到编程实现

在算法题中，递推公式是绝对的'主力'，下面的编程实战也将围绕递推公式展开。

三、错排问题的编程实现：从入门到进阶，3 种核心场景

3.1 场景 1：小规模 n（n≤20）—— 直接递推（入门题）

当 n≤20 时，错排数 Dₙ不会超过 1334961（n=10 时），用 64 位整数（long long）即可存储，无需取模，直接用递推公式计算即可。

例题：洛谷 P1595 信封问题

题目链接：https://www.luogu.com.cn/problem/P1595

题目描述：某人写了 n 封信和 n 个信封，所有信都装错了信封，求有多少种不同的情况（n≤20）。

输入示例：2 → 输出示例：1

解题思路：

初始化基础项 D₁=0，D₂=1；对于 n≥3，按递推公式 Dₙ=(n-1)*(Dₙ₋₁+Dₙ₋₂) 计算；直接输出结果。

C++ 代码实现

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 25; // 因为 n≤20，开 25 足够

int main() {
    int n;
    cin >> n;
    if (n == 1) { // 特殊情况处理
        cout << 0 << endl;
        return 0;
    }
    // 初始化基础项
    LL d[N];
    d[1] = 0;
    d[2] = 1;
    // 递推计算 D₃到 Dₙ
    for (int i = 3; i <= n; ++i) {
        d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
    }
    cout << d[n] << endl;
    return 0;
}

代码解析：

用 long long 存储错排数，避免溢出（n=20 时 D₂₀=51090942171709440000，刚好在 long long 的范围之内）；特殊处理 n=1 的情况，简化逻辑；递推过程时间复杂度 O(n)，对于 n≤20 来说，效率极高。

3.2 场景 2：中等规模 n（n≤200）—— 高精度递推（进阶题）

当 n>20 时，错排数会超过 long long 的存储范围（比如 n=21 时 D₂₁=1124000727777607680000，远超 64 位整数上限），此时需要用高精度计算来存储结果。

例题：洛谷 P3182 [HAOI2016] 放棋子

题目链接：https://www.luogu.com.cn/problem/P3182

题目描述：给一个 N×N 的矩阵，每行有一个障碍（任意两个障碍不同行不同列），在矩阵上放 N 枚棋子（障碍位置不能放），要求每行每列只有一枚棋子，求合法方案数（N≤200）。

输入示例：20 11 0

输出示例：1

解题思路：

题目中的障碍矩阵本质是一个'初始排列'（每行每列一个障碍），放棋子的要求是'每行每列一个棋子且不在障碍位置'—— 这等价于求初始排列的错排数！由于 N≤200，错排数极大，必须用高精度计算（数组模拟大整数）。

C++ 代码实现（高精度递推）

#include <iostream>
using namespace std;
const int N = 210; // 最大 n=200
const int M = 500; // 高精度数组长度，足够存储 n=200 的错排数

// 高精度加法：a = b + c（a、b、c 为逆序存储的大整数，低位在前）
void add(int a[], int b[], int c[]) {
    for (int i = 0; i < M - 1; ++i) {
        a[i] += b[i] + c[i];
        a[i + 1] += a[i] / 10; // 进位
        a[i] %= 10; // 取当前位
    }
}

// 高精度乘法：a = a × x（a 为逆序存储的大整数，x 为普通整数）
void mul(int a[], int x) {
    int carry = 0; // 进位
    for (int i = 0; i < M - 1; ++i) {
        carry += a[i] * x;
        a[i] = carry % 10; // 当前位
        carry /= 10; // 更新进位
    }
}

int main() {
    int n;
    cin >> n;
    // 读取障碍矩阵（其实用不到，只是题目输入要求）
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int tmp;
            cin >> tmp;
        }
    }
    // 初始化高精度数组：f[i] 存储 D_i，逆序存储（f[i][0] 是个位，f[i][1] 是十位...）
    int f[N][M] = {0};
    f[2][0] = 1; // D_2=1
    // 递推计算 D_3到 D_n
    for (int i = 3; i <= n; ++i) {
        // D_i = (i-1) * (D_{i-1} + D_{i-2})
        add(f[i], f[i-1], f[i-2]); // 先计算 D_{i-1} + D_{i-2}
        mul(f[i], i - 1); // 再乘以 (i-1)
    }
    // 输出结果：从高位到低位输出
    int p = M - 1;
    while (p >= 0 && f[n][p] == 0) --p; // 跳过前导零
    if (p < 0) cout << 0; // 理论上 n≥2 时不会出现
    else {
        while (p >= 0) cout << f[n][p--];
    }
    cout << endl;
    return 0;
}

代码解析：

高精度存储：用二维数组 f[N][M] 存储错排数，f[i][j] 表示 Dᵢ的第 j 位（逆序存储，低位在前，方便进位处理）； 高精度加法：处理 Dₙ₋₁ + Dₙ₋₂的和； 高精度乘法：处理（n-1）与和的乘积； 输出时从高位到低位遍历，跳过前导零，得到正确的结果。

3.3 场景 3：大规模 n（n≤1e6）+ 多组查询 + 取模（高阶题）

当 n≤1e6 且有多个查询（比如 T=1e5 组）时，需要提前预处理错排数数组，并用取模运算避免溢出（通常题目要求对 1e9+7 取模）。

例题：洛谷 P4071 [SDOI2016] 排列计数

题目链接：https://www.luogu.com.cn/problem/P4071

题目描述：求有多少种 1 到 n 的排列 a，满足恰好有 m 个位置 i 使得 a[i]=i（称为'不动点'），答案对 1e9+7 取模（T 组查询，n≤1e6）。

输入示例：5 1 0 → 0 1 1 → 1 5 2 → 20 100 50 → 578028887 10000 5000 → 60695423

解题思路：

恰好 m 个不动点：先从 n 个位置中选 m 个作为不动点（组合数 C(n,m)）；剩下的（n-m）个位置必须是错排（错排数 Dₙ₋ₘ）； 总方案数 = C(n,m) × Dₙ₋ₘ mod 1e9+7； 预处理：提前计算 1e6 以内的阶乘、阶乘逆元（用于快速计算组合数）和错排数。

C++ 代码实现（预处理 + 取模）

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const int MOD = 1e9 + 7;

LL fact[N]; // fact[i] = i! mod MOD
LL inv_fact[N]; // inv_fact[i] = (i!)^{-1} mod MOD
LL derange[N]; // derange[i] = D_i mod MOD

// 快速幂：计算 a^b mod p（费马小定理求逆元用）
LL qpow(LL a, LL b, LL p) {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

// 预处理阶乘、阶乘逆元、错排数
void init() {
    // 1. 预处理阶乘
    fact[0] = 1;
    for (int i = 1; i < N; ++i) {
        fact[i] = fact[i-1] * i % MOD;
    }
    // 2. 预处理阶乘逆元（费马小定理：a^(p-2) mod p 是 a 的逆元，p 为质数）
    inv_fact[N-1] = qpow(fact[N-1], MOD-2, MOD);
    for (int i = N-2; i >= 0; --i) {
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
    // 3. 预处理错排数
    derange[1] = 0;
    derange[2] = 1;
    for (int i = 3; i < N; ++i) {
        derange[i] = (i-1) * (derange[i-1] + derange[i-2]) % MOD;
    }
}

// 计算组合数 C(n, m) mod MOD
LL comb(int n, int m) {
    if (n < m) return 0;
    return fact[n] * inv_fact[m] % MOD * inv_fact[n - m] % MOD;
}

int main() {
    init(); // 预处理，O(N) 时间
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        if (n < m) {
            cout << 0 << endl;
            continue;
        }
        if (n == m) {
            cout << 1 << endl;
            continue;
        }
        // 总方案数 = C(n, m) * D(n-m) mod MOD
        LL ans = comb(n, m) * derange[n - m] % MOD;
        cout << ans << endl;
    }
    return 0;
}

代码解析：

预处理优化：提前计算 1e6 以内的阶乘、阶乘逆元、错排数，每组查询仅需 O(1) 时间计算； 组合数计算：利用阶乘和逆元快速计算 C(n,m) = n!/(m!(n-m)!) mod MOD； 取模运算：每一步计算都取模，避免溢出，同时保证结果符合题目要求； 时间复杂度：预处理 O(N)，查询 O(T)，适合大规模数据和多组查询场景。

四、错排问题的拓展应用：不止于'错位'

错排问题的核心思想（递推、容斥、高精度）可以迁移到很多类似问题中，比如：

4.1 部分错排问题

求 n 个元素中恰好有 k 个元素在原位，其余 n-k 个元素错排的方案数（如洛谷 P4071），解法为 C(n,k) × Dₙ₋ₖ。

4.2 环形错排问题

n 个人围坐一圈，求每个人都不坐在原来位置上的排列数（环形错排），公式为：D'ₙ = (n-1) × (Dₙ₋₁ + Dₙ₋₃)

4.3 带限制的错排问题

如元素 i 不能放到位置 j（j 是多个禁止位置），可结合容斥原理和动态规划求解。

五、常见误区与避坑指南

5.1 溢出问题

小规模 n（n≤20）：用 long long； 中等规模 n（20<n≤200）：用高精度； 大规模 n（n≤1e6）：用取模 + 递推。

5.2 边界条件处理

忘记处理 n=1（D₁=0）、n=2（D₂=1）的基础情况；组合数计算时 n<m 的情况（返回 0）。

5.3 高精度计算的细节

大整数的存储顺序（逆序存储更方便进位）；加法和乘法的进位处理（避免漏进位导致结果错误）。

总结

错排问题看似复杂，但只要抓住'递推公式'这个核心，再根据 n 的规模选择合适的实现方式（直接递推、高精度、取模预处理），就能轻松解决各类题目。

通过本文的学习，不仅能掌握错排问题的解法，更能理解组合数学中'从特殊到一般、从递推到优化'的思维方式。下次遇到类似的排列组合问题，不妨试试用错排的思路来分析，或许能迎刃而解！