信奥赛C++提高组csp-s之组合数学专题课：圆排列

信奥赛C提高组csp-s之组合数学专题课圆排列一、数学原理1.1 圆排列的核心公式从 (n) 个不同元素中取出 (n) 个围成一个圆圈所有元素全用上的圆排列数为圆排列数 n ! n ( n − 1 ) ! \text{圆排列数} \frac{n!}{n} (n-1)!圆排列数nn!​(n−1)!推导逻辑线性排列数n!n个元素排成一排在圆桌上旋转后相同的排列只计1种。每种圆排列对应n种线性排列分别以圆上不同元素作为线性排列的起点。因此圆排列数 n ! ÷ n ( n − 1 ) ! n! \div n (n-1)!n!÷n(n−1)!1.2 部分元素的圆排列若只从 n 个不同元素中选出 m 个围成一圈m ≤ n m \le nm≤n排列数为圆排列数 C n m × m ! m n ! ( n − m ) ! × m \text{圆排列数} \frac{C_n^m \times m!}{m} \frac{n!}{(n-m)! \times m}圆排列数mCnm​×m!​(n−m)!×mn!​解释先从 n个中选 m 个C n m C_n^mCnm​对选出的 m 个做圆排列(m-1)!C n m × ( m − 1 ) ! n ! m ! ( n − m ) ! × ( m − 1 ) ! n ! m ( n − m ) ! C_n^m \times (m-1)! \frac{n!}{m!(n-m)!} \times (m-1)! \frac{n!}{m(n-m)!}Cnm​×(m−1)!m!(n−m)!n!​×(m−1)!m(n−m)!n!​1.3 可翻转的圆排列项链排列若圆排列可以翻转翻转后相同也视为同一种如串珠子则在圆排列基础上再除以2项链排列数 ( n − 1 ) ! 2 ( n ≥ 3 ) \text{项链排列数} \frac{(n-1)!}{2} \quad (n \ge 3)项链排列数2(n−1)!​(n≥3)当 n1 或 n2 时翻转与旋转等价公式需单独考虑 。二、数学例子例1基础圆排列5个人围圆桌就餐有多少种坐法解(5-1)! 4! 24种。例2部分元素的圆排列从7个人中选4人围成一圈玩游戏有多少种不同的圈解7 ! ( 7 − 4 ) ! × 4 5040 6 × 4 210 \frac{7!}{(7-4)! \times 4} \frac{5040}{6 \times 4} 210(7−4)!×47!​6×45040​210种。或者先选4人C 7 4 35 C_7^4 35C74​35再圆排列( 4 − 1 ) ! 6 (4-1)! 6(4−1)!635 × 6 210 35 \times 6 21035×6210。例3有特殊条件的圆排列3对夫妻围圆桌要求夫妻相邻有多少种坐法解将每对夫妻视为一个整体3个整体3个整体圆排列( 3 − 1 ) ! 2 ! (3-1)! 2!(3−1)!2!每对夫妻内部可交换2 × 2 × 2 8 2 \times 2 \times 2 82×2×28总数2 ! × 8 16 2! \times 8 162!×816种 。三、编程案例圆排列计数题目描述给定整数 n求 n 个不同元素围成一圈的方案数结果对10 9 7 10^971097取模。输入一个整数 n1 ≤ n ≤ 10 6 1 \le n \le 10^61≤n≤106输出输出圆排列数结果对10 9 7 10^971097取模样例输入5 输出24思路分析本题是圆排列公式的直接应用核心是计算阶乘。当 n1 时(n-1)! 0! 1一个人无论怎么旋转都是1种。由于 n 最大可达10 6 10^6106必须预计算阶乘并取模避免重复计算。使用递推f a c [ i ] f a c [ i − 1 ] × i % M fac[i] fac[i-1] \times i \% Mfac[i]fac[i−1]×i%M。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintM1e97;// 模数constintN1e65;// 数组大小ll f[N];// f[i] 存储 i! % Mintmain(){intn;cinn;// 预计算阶乘f[0]1;// 0! 1for(inti1;in;i){f[i]f[i-1]*i%M;// 递推取模}// 圆排列数为 (n-1)! 注意 n0 的情况本题不存在ll ansf[n-1];// 直接查表coutansendl;return0;}功能分析时间复杂度O(n)预计算阶乘一次完成查询 O(1)。空间复杂度O(n)存储阶乘表。核心处理模运算防止溢出满足大数要求。利用递推高效计算阶乘适合多组查询若题目改为多组查询可一次性预处理到最大值。边界处理当 n1 时f[0] 1输出1。更多系列知识请查看专栏《信奥赛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;}