信奥赛C提高组csp-s之组合数学专题课错排列一、数学原理1. 定义错排列是指一个排列a 1 , a 2 , … , a n a_1, a_2, \dots, a_na1​,a2​,…,an​中每一个元素都不在它原本的位置上。即对于所有的 i 满足 $ a_i \neq i$。通常将 n 个元素的错排数记作D n D_nDn​或! n !n!n。2. 递推公式推导错排的递推公式是D n ( n − 1 ) × ( D n − 1 D n − 2 ) , ( n ≥ 3 ) D_n (n-1) \times (D_{n-1} D_{n-2}), \quad (n \ge 3)Dn​(n−1)×(Dn−1​Dn−2​),(n≥3)边界条件D 1 0 , D 2 1 D_1 0, \quad D_2 1D1​0,D2​1推导过程经典的两步法考虑第 n 个元素的位置第一步将元素 n 放到某个位置 k k ≠ n k \neq nkn共有 n-1 种选择。第二步处理元素 k 的放置情况分两种子情况情况 A元素 k 恰好放在了位置 n 。此时元素 n 和 k 互换位置剩下的 n-2 个元素需要构成错排方案数为D n − 2 D_{n-2}Dn−2​。情况 B元素 k不放在位置 n 。这意味着对于剩下的 n-1 个元素包括 k 它们必须全部错排且不能放在各自原本的位置。由于 k 原本的位置是 k 现在它不能去 n 且不能去 k 相当于规模为 ( n-1 ) 的错排问题方案数为D n − 1 D_{n-1}Dn−1​。根据加法原理对于固定的 k 有D n − 2 D n − 1 D_{n-2} D_{n-1}Dn−2​Dn−1​种方法再结合乘法原理D n ( n − 1 ) × ( D n − 1 D n − 2 ) D_n (n-1) \times (D_{n-1} D_{n-2})Dn​(n−1)×(Dn−1​Dn−2​)二、数学例子1. 枚举小 ( n ) 的错排数n 1唯一排列 [1] 不是错排D 1 0 D_1 0D1​0。n 2排列有 [1,2] 和 [2,1]。只有 [2,1] 是错排D 2 1 D_2 1D2​1。n 3全排列共 6 种。错排有[2,3,1] 和 [3,1,2] 两种D 3 2 D_3 2D3​2。n 4根据递推公式D 4 3 × ( D 3 D 2 ) 3 × ( 2 1 ) 9 D_4 3 \times (D_3 D_2) 3 \times (21) 9D4​3×(D3​D2​)3×(21)9。n 5D 5 4 × ( D 4 D 3 ) 4 × ( 9 2 ) 44 D_5 4 \times (D_4 D_3) 4 \times (92) 44D5​4×(D4​D3​)4×(92)44。2. 手工验证 ( n 4 ) 的错排列出所有 9 种错排原排列为 1,2,3,4(2,1,4,3), (2,3,4,1), (2,4,1,3),(3,1,4,2), (3,4,1,2), (3,4,2,1),(4,1,2,3), (4,3,1,2), (4,3,2,1)。三、编程案例信封问题题目描述某人写了n nn封信和n nn个信封如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。输入格式一个信封数n nn保证n ≤ 20 n \le 20n≤20。输出格式一个整数代表有多少种情况。输入输出样例 1输入 12输出 11输入输出样例 2输入 23输出 22说明/提示对于100 % 100 \%100%的数据1 ≤ n ≤ 20 1 \le n \le 201≤n≤20。思路分析使用错排直接套用递推公式即可。注意数据范围n ≤ 20 n \leq 20n≤20D 20 D_{20}D20​的值约为8.95 × 10 18 8.95 \times 10^{18}8.95×1018超出了 32 位 int 的范围必须使用long long。代码实现#includebits/stdc.husingnamespacestd;intn;longlongd[25];// 用 long long 防止溢出intmain(){cinn;// 边界条件d[1]0;if(n2)d[2]1;// 递推计算for(inti3;in;i){d[i](i-1)*(d[i-1]d[i-2]);}coutd[n]endl;return0;}功能分析时间复杂度( O(n) )只需一次循环。空间复杂度( O(n) )存储错排数数组。要点使用long long保证精度。更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}