C++算法
错排问题详解：从递推公式到编程实现
错排问题指 n 个元素重排后均不在原位的计数问题。核心递推公式为 Dₙ=(n-1)(Dₙ₋₁+Dₙ₋₂)。根据数据规模不同，实现方式分为小规模直接递推、中等规模高精度计算及大规模取模预处理。应用场景包括部分错排与环形错排等变体。解题需注意整数溢出与边界条件处理。
错排问题指 n 个元素重排后均不在原位的计数问题。核心递推公式为 Dₙ=(n-1)(Dₙ₋₁+Dₙ₋₂)。根据数据规模不同，实现方式分为小规模直接递推、中等规模高精度计算及大规模取模预处理。应用场景包括部分错排与环形错排等变体。解题需注意整数溢出与边界条件处理。
错排问题的正式描述是：有 n 个不同的元素（如编号 1~n 的信、书、奖券），将它们重新排列，使得每个元素都不在原来的位置上，这样的排列称为'错排'（Derangement），求这样的排列一共有多少种？
我们用 Dₙ表示 n 个元素的错排数，例如：
随着 n 的增大，错排数 Dₙ的增长速度非常快，形成了独特的错排序列：
| n（元素个数） | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Dₙ（错排数） | 0 | 1 | 2 | 9 | 44 | 265 | 1854 | 14833 | 133496 | 1334961 |
这个序列看似无规律，但背后隐藏着严谨的数学递推关系，这也是我们解决错排问题的核心。
错排问题的递推公式是解决编程问题的关键，我们通过'分步讨论'的方式推导：
假设我们有 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）种选择，且两种情况是互斥的，因此总的错排数为：Dₙ = (n-1) × (Dₙ₋₁ + Dₙ₋₂)
这就是错排问题的核心递推公式！有了这个公式，我们可以从 D₁=0、D₂=1 出发，递推出任意 n 的错排数。
除了递推公式，错排问题还有通项公式，可通过容斥原理推导得出：Dₙ = n! × (1 - 1/1! + 1/2! - 1/3! + ... + (-1)ⁿ/n!)
这个公式的意义是：n 个元素的全排列数（n!）减去至少 1 个元素在原位的排列数，加上至少 2 个元素在原位的排列数，减去至少 3 个元素在原位的排列数……以此类推（容斥原理的核心思想）。
虽然通项公式看起来更'高级'，但在编程实践中，递推公式更实用（尤其是 n 较大时，通项公式的计算容易出现精度问题，而递推公式可通过取模避免）。
| 公式类型 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 递推公式 | 计算简单、无精度损失、支持取模 | 需从基础项递推，无法直接求 Dₙ | 编程实现、n≤1e6 的场景 |
| 通项公式 | 可直接计算 Dₙ，无需递推 | 浮点数精度问题、n 较大时计算复杂 | 数学推导、n 较小（≤20）的场景 |
在算法题中，递推公式是绝对的'主力'，下面的编程实战也将围绕递推公式展开。
当 n≤20 时，错排数 Dₙ不会超过 1334961（n=10 时），用 64 位整数（long long）即可存储，无需取模，直接用递推公式计算即可。
题目链接：https://www.luogu.com.cn/problem/P1595
题目描述：某人写了 n 封信和 n 个信封，所有信都装错了信封，求有多少种不同的情况（n≤20）。
输入示例：2 → 输出示例：1
解题思路：
初始化基础项 D₁=0，D₂=1；对于 n≥3，按递推公式 Dₙ=(n-1)*(Dₙ₋₁+Dₙ₋₂) 计算；直接输出结果。
#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 来说，效率极高。
当 n>20 时，错排数会超过 long long 的存储范围（比如 n=21 时 D₂₁=1124000727777607680000，远超 64 位整数上限），此时需要用高精度计算来存储结果。
题目链接：https://www.luogu.com.cn/problem/P3182
题目描述：给一个 N×N 的矩阵，每行有一个障碍（任意两个障碍不同行不同列），在矩阵上放 N 枚棋子（障碍位置不能放），要求每行每列只有一枚棋子，求合法方案数（N≤200）。
输入示例：20 11 0
输出示例：1
解题思路：
题目中的障碍矩阵本质是一个'初始排列'（每行每列一个障碍），放棋子的要求是'每行每列一个棋子且不在障碍位置'—— 这等价于求初始排列的错排数！由于 N≤200，错排数极大，必须用高精度计算（数组模拟大整数）。
#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 ( i = ; i <= n; ++i) {
( j = ; j <= n; ++j) {
tmp;
cin >> tmp;
}
}
f[N][M] = {};
f[][] = ;
( i = ; i <= n; ++i) {
(f[i], f[i], f[i]);
(f[i], i - );
}
p = M - ;
(p >= && f[n][p] == ) --p;
(p < ) cout << ;
{
(p >= ) cout << f[n][p--];
}
cout << endl;
;
}
代码解析：
高精度存储：用二维数组 f[N][M] 存储错排数，f[i][j] 表示 Dᵢ的第 j 位（逆序存储，低位在前，方便进位处理）； 高精度加法：处理 Dₙ₋₁ + Dₙ₋₂的和； 高精度乘法：处理（n-1）与和的乘积； 输出时从高位到低位遍历，跳过前导零，得到正确的结果。
当 n≤1e6 且有多个查询（比如 T=1e5 组）时，需要提前预处理错排数数组，并用取模运算避免溢出（通常题目要求对 1e9+7 取模）。
题目链接：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 以内的阶乘、阶乘逆元（用于快速计算组合数）和错排数。
#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;
}
derange[] = ;
derange[] = ;
( i = ; i < N; ++i) {
derange[i] = (i) * (derange[i] + derange[i]) % MOD;
}
}
{
(n < m) ;
fact[n] * inv_fact[m] % MOD * inv_fact[n - m] % MOD;
}
{
();
T;
cin >> T;
(T--) {
n, m;
cin >> n >> m;
(n < m) {
cout << << endl;
;
}
(n == m) {
cout << << endl;
;
}
LL ans = (n, m) * derange[n - m] % MOD;
cout << ans << endl;
}
;
}
代码解析：
预处理优化：提前计算 1e6 以内的阶乘、阶乘逆元、错排数，每组查询仅需 O(1) 时间计算； 组合数计算：利用阶乘和逆元快速计算 C(n,m) = n!/(m!(n-m)!) mod MOD； 取模运算：每一步计算都取模，避免溢出，同时保证结果符合题目要求； 时间复杂度：预处理 O(N)，查询 O(T)，适合大规模数据和多组查询场景。
错排问题的核心思想（递推、容斥、高精度）可以迁移到很多类似问题中，比如：
求 n 个元素中恰好有 k 个元素在原位，其余 n-k 个元素错排的方案数（如洛谷 P4071），解法为 C(n,k) × Dₙ₋ₖ。
n 个人围坐一圈，求每个人都不坐在原来位置上的排列数（环形错排），公式为：D'ₙ = (n-1) × (Dₙ₋₁ + Dₙ₋₃)
如元素 i 不能放到位置 j（j 是多个禁止位置），可结合容斥原理和动态规划求解。
小规模 n（n≤20）：用 long long； 中等规模 n（20<n≤200）：用高精度； 大规模 n（n≤1e6）：用取模 + 递推。
忘记处理 n=1（D₁=0）、n=2（D₂=1）的基础情况；组合数计算时 n<m 的情况（返回 0）。
大整数的存储顺序（逆序存储更方便进位）；加法和乘法的进位处理（避免漏进位导致结果错误）。
错排问题看似复杂，但只要抓住'递推公式'这个核心，再根据 n 的规模选择合适的实现方式（直接递推、高精度、取模预处理），就能轻松解决各类题目。
通过本文的学习，不仅能掌握错排问题的解法，更能理解组合数学中'从特殊到一般、从递推到优化'的思维方式。下次遇到类似的排列组合问题，不妨试试用错排的思路来分析，或许能迎刃而解！
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online