核心内容摘要
丘丘人把申鹤焯出白水的原因
目录编辑前言
错排问题的定义什么是 “完全错位”
1 严格定义
2 错排序列的规律
错排公式的推导从 “递推” 到 “通项”两种思路吃透本质
1 递推公式最易理解的核心逻辑
2 通项公式数学视角的精准表达
3 两种公式的对比与适用场景
错排问题的编程实现从入门到进阶3 种核心场景
1 场景 1小规模 nn≤20—— 直接递推入门题例题洛谷 P1595 信封问题C 代码实现
2 场景 2中等规模 nn≤200—— 高精度递推进阶题例题洛谷 P3182 [HAOI2016] 放棋子C 代码实现高精度递推
3 场景 3大规模 nn≤1e6 多组查询 取模高阶题例题洛谷 P4071 [SDOI2016] 排列计数C 代码实现预处理 取模
错排问题的拓展应用不止于 “错位”
1 部分错排问题
2 环形错排问题
3 带限制的错排问题
常见误区与避坑指南
1 溢出问题
2 边界条件处理
3 高精度计算的细节
总结你有没有过这样的经历给 5 个朋友写信却把所有信件都装错了信封整理书架时想把 5 本书放回原位结果每本书都不在原来的位置甚至抽奖时5 个人抽 5 张奖券竟然没人抽到自己的名字 —— 这些看似 “倒霉” 的巧合背后都隐藏着组合数学中的经典问题错排问题。
错排问题又称伯努利信封问题是组合数学中最具趣味性且应用广泛的核心问题之一。
它看似简单实则涉及深刻的递归思想和计数逻辑不仅是算法面试中的 “常客”如字节跳动、腾讯等公司的笔试真题还广泛应用于密码学、随机抽样、任务调度等领域。
本文将从生活场景出发带你层层拆解错排问题的本质推导错排公式详解递推逻辑再通过 3 道经典例题手把手教你实现高效解法。
无论你是算法新手还是想巩固组合数学基础的开发者读完这篇文章都能彻底掌握错排问题的核心技巧下面就让我们正式开始吧
错排问题的定义什么是 “完全错位”
1 严格定义错排问题的正式描述的是有 n 个不同的元素如编号 1~n 的信、书、奖券将它们重新排列使得每个元素都不在原来的位置上这样的排列称为“错排”Derangement求这样的排列一共有多少种我们用 Dₙ表示 n 个元素的错排数例如当 n1 时只有 1 个元素无法错位D₁0当 n2 时两个元素交换位置只有 1 种错排D₂1当 n3 时元素
1、
3 的错排为2,3,1和3,1,2共 2 种D₃2当 n4 时错排数为 9 种D₄9当 n5 时错排数为 44 种D₅44。
2 错排序列的规律随着 n 的增大错排数 Dₙ的增长速度非常快形成了独特的错排序列n元素个数12345678910Dₙ错排数0129442651854148331334961334961这个序列看似无规律但背后隐藏着严谨的数学递推关系这也是我们解决错排问题的核心。
错排公式的推导从 “递推” 到 “通项”两种思路吃透本质
1 递推公式最易理解的核心逻辑错排问题的递推公式是解决编程问题的关键我们通过 “分步讨论” 的方式推导假设我们有 n 个元素编号 1~n现在要将它们全部错排考虑元素 1 的放置位置第一步将元素 1 放到除了位置 1 之外的任意一个位置共有n-1种选择比如放到位置 i2≤i≤n第二步处理位置 i 上的原元素编号 i此时有两种情况情况 1将元素 i 放到位置 1。
此时元素 1 和元素 i 完成了 “交换”剩下的n-2个元素2~i-
i1~n需要进行错排错排数为 Dₙ₋₂情况 2不将元素 i 放到位置 1。
此时元素 i 不能放到位置 1 和位置 i而其他元素2~i-
i1~n也不能放到各自的原位置 —— 这相当于把位置 1 看作元素 i 的 “新原位置”剩下的n-1个元素2~n需要进行错排错排数为 Dₙ₋₁。
由于第一步有n-1种选择且两种情况是互斥的因此总的错排数为Dn(n−
×(Dn−1Dn−2)这就是错排问题的核心递推公式有了这个公式我们可以从 D₁
D₂1 出发递推出任意 n 的错排数。
2 通项公式数学视角的精准表达除了递推公式错排问题还有通项公式可通过容斥原理推导得出Dnn!×(1−1!12!1−3!1⋯(−
n×n!1)这个公式的意义是n 个元素的全排列数n!减去至少 1 个元素在原位的排列数加上至少 2 个元素在原位的排列数减去至少 3 个元素在原位的排列数…… 以此类推容斥原理的核心思想。
虽然通项公式看起来更 “高级”但在编程实践中递推公式更实用尤其是 n 较大时通项公式的计算容易出现精度问题而递推公式可通过取模避免。
3 两种公式的对比与适用场景公式类型优点缺点适用场景递推公式计算简单、无精度损失、支持取模需从基础项递推无法直接求 Dₙ编程实现、n≤1e6 的场景通项公式可直接计算 Dₙ无需递推浮点数精度问题、n 较大时计算复杂数学推导、n 较小≤20的场景在算法题中递推公式是绝对的 “主力”下面的编程实战也将围绕递推公式展开。
错排问题的编程实现从入门到进阶3 种核心场景
1 场景 1小规模 nn≤20—— 直接递推入门题当 n≤20 时错排数 Dₙ不会超过 1334961n10 时用 64 位整数long long即可存储无需取模直接用递推公式计算即可。
例题洛谷 P1595 信封问题题目链接https://www.luogu.com.cn/problem/P1595题目描述某人写了 n 封信和 n 个信封所有信都装错了信封求有多少种不同的情况n≤20。
输入示例2 → 输出示例1解题思路初始化基础项 D₁0D₂1对于 n≥3按递推公式Dₙ(n-
*(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
{ // 特殊情况处理 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 -
* (d[i - 1] d[i - 2]); } cout d[n] endl; return 0; }代码解析用 long long 存储错排数避免溢出n20 时 D₂₀51090942171709440000刚好在 long long 的范围之内特殊处理 n1 的情况简化逻辑递推过程时间复杂度 O (n)对于 n≤20 来说效率极高。
2 场景 2中等规模 nn≤200—— 高精度递推进阶题当 n20 时错排数会超过 long long 的存储范围比如 n21 时 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; // 最大n200 const int M 500; // 高精度数组长度足够存储n200的错排数 // 高精度加法a b ca、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 × xa为逆序存储的大整数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_21 // 递推计算D_3到D_n for (int i 3; i n; i) { // D_i (i-
* (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 -
; // 再乘以(i-
} // 输出结果从高位到低位输出 int p M - 1; while (p 0 f[n][p]
--p; // 跳过前导零 if (p
cout 0; // 理论上n≥2时不会出现 else { while (p
cout f[n][p--]; } cout endl; return 0; }代码解析高精度存储用二维数组 f [N][M] 存储错排数f [i][j] 表示 Dᵢ的第 j 位逆序存储低位在前方便进位处理高精度加法处理 Dₙ₋₁ Dₙ₋₂的和高精度乘法处理n-1与和的乘积输出时从高位到低位遍历跳过前导零得到正确的结果。
3 场景 3大规模 nn≤1e6 多组查询 取模高阶题当 n≤1e6 且有多个查询比如 T1e5 组时需要提前预处理错排数数组并用取模运算避免溢出通常题目要求对 1e97 取模。
例题洛谷 P4071 [SDOI2016] 排列计数题目链接https://www.luogu.com.cn/problem/P4071题目描述求有多少种 1 到 n 的排列 a满足恰好有 m 个位置 i 使得 a [i]i称为 “不动点”答案对 1e97 取模T 组查询n≤1e6。
输入示例51 0 → 01 1 → 15 2 → 20100 50 → 57802888710000 5000 → 60695423解题思路恰好 m 个不动点先从 n 个位置中选 m 个作为不动点组合数 C (n,m)剩下的n-m个位置必须是错排错排数 Dₙ₋ₘ总方案数 C (n,m) × Dₙ₋ₘ mod 1e97预处理提前计算 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
res res * a % p; a a * a % p; b 1; } return res; } // 预处理阶乘、阶乘逆元、错排数 void init() { //
预处理阶乘 fact[0] 1; for (int i 1; i N; i) { fact[i] fact[i-1] * i % MOD; } //
预处理阶乘逆元费马小定理a^(p-
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[i1] * (i
% MOD; } //
预处理错排数 derange[1] 0; derange[2] 1; for (int i 3; i N; i) { derange[i] (i-
* (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 (
时间计算组合数计算利用阶乘和逆元快速计算C (n,m) n!/(m!*(n-m)!) mod MOD取模运算每一步计算都取模避免溢出同时保证结果符合题目要求时间复杂度预处理 O (N)查询 O (T)适合大规模数据和多组查询场景。
错排问题的拓展应用不止于 “错位”错排问题的核心思想递推、容斥、高精度可以迁移到很多类似问题中比如
1 部分错排问题求 n 个元素中恰好有 k 个元素在原位其余 n-k 个元素错排的方案数如洛谷 P4071解法为C (n,k) × Dₙ₋ₖ。
2 环形错排问题n 个人围坐一圈求每个人都不坐在原来位置上的排列数环形错排公式为Dn′(n−
×(Dn−1Dn−3)
3 带限制的错排问题如元素 i 不能放到位置 jj 是多个禁止位置可结合容斥原理和动态规划求解。
常见误区与避坑指南
1 溢出问题小规模 nn≤20用 long long中等规模 n20n≤200用高精度大规模 nn≤1e6用取模 递推。
2 边界条件处理忘记处理 n1D₁
n2D₂1的基础情况组合数计算时 nm 的情况返回 0。
3 高精度计算的细节大整数的存储顺序逆序存储更方便进位加法和乘法的进位处理避免漏进位导致结果错误。
总结错排问题看似复杂但只要抓住 “递推公式” 这个核心再根据 n 的规模选择合适的实现方式直接递推、高精度、取模预处理就能轻松解决各类题目。
通过本文的学习相信你不仅能掌握错排问题的解法更能理解组合数学中 “从特殊到一般、从递推到优化” 的思维方式。
下次遇到类似的排列组合问题不妨试试用错排的思路来分析或许能迎刃而解如果本文对你有帮助欢迎点赞、收藏、转发也欢迎在评论区交流讨论 后续还会分享更多组合数学经典问题如卡特兰数、容斥原理关注我一起玩转算法