一、错排问题的定义：什么是'完全错位'？
1.1 严格定义
错排问题的正式描述是：有 n 个不同的元素（如编号 1~n 的信、书、奖券），将它们重新排列，使得每个元素都不在原来的位置上，这样的排列称为'错排'（Derangement），求这样的排列一共有多少种？
我们用 Dₙ表示 n 个元素的错排数，例如：
- 当 n=1 时：只有 1 个元素，无法错位，D₁=0；
- 当 n=2 时：两个元素交换位置，只有 1 种错排，D₂=1；
- 当 n=3 时：元素 1、2、3 的错排为（2,3,1）和（3,1,2），共 2 种，D₃=2；
- 当 n=4 时：错排数为 9 种，D₄=9；
- 当 n=5 时：错排数为 44 种，D₅=44。
1.2 错排序列的规律
随着 n 的增大，错排数 Dₙ的增长速度非常快，形成了独特的错排序列：
| n（元素个数） | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Dₙ（错排数） | 0 | 1 | 2 | 9 | 44 | 265 | 1854 | 14833 | 133496 | 1334961 |
这个序列看似无规律，但背后隐藏着严谨的数学递推关系，这也是我们解决错排问题的核心。
二、错排公式的推导：从'递推'到'通项'，两种思路吃透本质
2.1 递推公式：最易理解的核心逻辑
错排问题的递推公式是解决编程问题的关键，我们通过'分步讨论'的方式推导：
假设我们有 n 个元素（编号 1~n），现在要将它们全部错排，考虑元素 1 的放置位置：
**第一步：**将元素 1 放到除了位置 1 之外的任意一个位置，共有（n-1）种选择（比如放到位置 i，2≤i≤n）； **第二步：**处理位置 i 上的原元素（编号 i），此时有两种情况： 情况 1：将元素 i 放到位置 1。此时，元素 1 和元素 i 完成了'交换'，剩下的（n-2）个元素（2
i-1、i+1n）需要进行错排，错排数为 Dₙ₋₂； 情况 2：不将元素 i 放到位置 1。此时，元素 i 不能放到位置 1 和位置 i，而其他元素（2i-1、i+1n）也不能放到各自的原位置 —— 这相当于把位置 1 看作元素 i 的'新原位置'，剩下的（n-1）个元素（2~n）需要进行错排，错排数为 Dₙ₋₁。
由于第一步有（n-1）种选择，且两种情况是互斥的，因此总的错排数为：Dn=(n−1)×(Dn−1+Dn−2)
这就是错排问题的核心递推公式！有了这个公式，我们可以从 D₁=0、D₂=1 出发，递推出任意 n 的错排数。
2.2 通项公式：数学视角的精准表达
除了递推公式，错排问题还有通项公式，可通过容斥原理推导得出：Dn=n!×(1−1/1!+1/2!−1/3!+⋯+(−1)n×1/n!)
这个公式的意义是：n 个元素的全排列数（n!）减去至少 1 个元素在原位的排列数，加上至少 2 个元素在原位的排列数，减去至少 3 个元素在原位的排列数……以此类推（容斥原理的核心思想）。
虽然通项公式看起来更'高级'，但在编程实践中，递推公式更实用（尤其是 n 较大时，通项公式的计算容易出现精度问题，而递推公式可通过取模避免）。
2.3 两种公式的对比与适用场景
| 公式类型 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 递推公式 | 计算简单、无精度损失、支持取模 | 需从基础项递推，无法直接求 Dₙ | 编程实现、n≤1e6 的场景 |
| 通项公式 | 可直接计算 Dₙ，无需递推 | 浮点数精度问题、n 较大时计算复杂 | 数学推导、n 较小（≤20）的场景 |
在算法题中，递推公式是绝对的'主力'，下面的编程实战也将围绕递推公式展开。
三、错排问题的编程实现：从入门到进阶，3 种核心场景
3.1 场景 1：小规模 n（n≤20）—— 直接递推（入门题）
当 n≤20 时，错排数 Dₙ不会超过 1334961（n=10 时），用 64 位整数（long long）即可存储，无需取模，直接用递推公式计算即可。
例题：洛谷 P1595 信封问题
题目来源：洛谷 P1595 信封问题
题目描述：某人写了 n 封信和 n 个信封，所有信都装错了信封，求有多少种不同的情况（n≤20）。
输入示例：2 → 输出示例：1
解题思路：
初始化基础项 D₁=0，D₂=1；对于 n≥3，按递推公式 Dn=(n-1)*(Dn-1+Dn-2) 计算；直接输出结果。
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] 放棋子
题目来源：洛谷 P3182 [HAOI2016] 放棋子
题目描述：给一个 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] 排列计数
题目来源：洛谷 P4071 [SDOI2016] 排列计数
题目描述：求有多少种 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 个人围坐一圈，求每个人都不坐在原来位置上的排列数（环形错排），公式为：Dn′=(n−1)×(Dn−1+Dn−3)
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 的规模选择合适的实现方式（直接递推、高精度、取模预处理），就能轻松解决各类题目。通过本文的学习，希望能帮助你掌握错排问题的解法，理解组合数学中'从特殊到一般、从递推到优化'的思维方式。