组合数求法汇总
一:递推求解
对于组合数,有此式: C n m = C n − 1 m − 1 + C n − 1 m C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m} Cnm=Cn−1m−1+Cn−1m。
C n m C_{n}^{m} Cnm 可理解为 n n n 个数中选 m m m 个,不同的方案。对于第 n n n 个,可以选或不选,分别对应了 C n − 1 m − 1 C_{n-1}^{m-1} Cn−1m−1 和 C n − 1 m C_{n-1}^{m} Cn−1m 的方案,根据加法原理,令它们相加就得到了 C n m C_{n}^{m} Cnm。
此方法适用于 n n n 的范围不是很大的情况,而限制没有,即方便写高精度,也可以对任意模数取模,唯一缺点便是时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
附代码:
for(int i=0;i<=n;i++){for(int j=0;j<=i;j++){if(j==0) C[i][j]=1;else C[i][j]=C[i-1][j]+C[i-1][j-1];}
}
二:利用公式,用逆元求解
根据组合数公式 C n m = n ! m ! ( n − m ) ! C_{n}^{m}=\frac{n!}{m!(n-m)!} Cnm=m!(n−m)!n!,在取模的意义下,除一个数等于乘它的逆元,我们就可以线性求出阶乘逆元,然后 O ( 1 ) O(1) O(1)求解组合数。
而此方法要求模数是质数,并且逆元必须存在。一般在模一个很大的质数
(例如 998244353 998244353 998244353 或 1 e 9 + 7 1e9+7 1e9+7)的情况下可以优先考虑它。
附代码:
int qpow(int a,int b){int res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod,b>>=1;}return res;
}
int C(int n,int m){if(n<m) return 0;return fac[n]*infac[m]%mod*infac[n-m]%mod;
}
void init(){fac[0]=1;int t=1e6;//1<=n<=1e6for(int i=1;i<=t;i++) fac[i]=fac[i-1]*i%mod;infac[t]=qpow(fac[t],mod-2);for(int i=t-1;i>=0;i--) infac[i]=infac[i+1]*(i+1)%mod;
}
三:Lucas定理
我们上文说了逆元求组合数需要模上一个质数,那么在模数任意的情况下如何求解?
这就需要利用 Lucas 定理来求解。
先上 Lucas 定理给出的式子: C n m ≡ C n m o d p m m o d p ∗ C n / p m / p ( m o d p ) C_{n}^{m}\equiv C_{n_{} mod_{}p}^{m_{}mod_{}p}*C_{n/p}^{m/p}(mod_{}p) Cnm≡Cnmodpmmodp∗Cn/pm/p(modp)。
由此,我们可以先预处理出 [ 1 , p ] [1,p] [1,p] 范围内的阶乘逆元,然后递归求解。另外,Lucas 定理也有适用范围,它一般适用于模数并不是很大(一般是小质数,范围在 1 e 5 1e5 1e5 左右,这个时候可以放心求解)。并且它还可以用于 n , m n,m n,m 非常大,模数非常小,的情况。
具体可看代码实现:
int Lucas(int n,int m,int p){if(m==0) return 1;return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;//C(n%p,m%p)见上文
}
附:练习
下面是一些求组合数的练习题。
Lucas 定理:
(纯模版题)
P3223 [HNOI2012] 排队:
(梦回高中数学,需要推出式子,然后高精度求)
P2822 [NOIP2016 提高组]组合数问题:
(递推+高精度求组合数,需要一定优化技巧)
P1680 奇怪的分组:
(插板法,蛮简单的)
P1655 小朋友的球:
(斯特林数,如果不知道的话很难推出来,可以学一学)
相关文章:
组合数求法汇总
一:递推求解 对于组合数,有此式: C n m C n − 1 m − 1 C n − 1 m C_{n}^{m}C_{n-1}^{m-1}C_{n-1}^{m} CnmCn−1m−1Cn−1m。 C n m C_{n}^{m} Cnm 可理解为 n n n 个数中选 m m m 个,不同的方案。对于第 n n n 个…...
Python知识点:在Python编程中,如何使用Joblib进行并行计算
开篇,先说一个好消息,截止到2025年1月1日前,翻到文末找到我,赠送定制版的开题报告和任务书,先到先得!过期不候! Joblib是一个Python库,它被设计用来提供轻便的并行计算解决方案&…...
matlab-对比两张图片的CIElab分量的差值并形成直方图
%对比两张图片的CIElab分量的差值并形成直方图,改个路径就能用,图片分辨率要一致 close all; clear all; clc; I1imread(E:\test\resources\image\1.jpg); I2imread(E:\test\resources\image\2.jpg); lab1 rgb2lab(I1); lab2 rgb2lab(I2); % 提取色度…...
(十七)、Mac 安装k8s
文章目录 1、Enable Kubernetes2、查看k8s运行状态3、启用 kubernetes-dashboard3.1、如果启动成功,可以在浏览器访问3.2、如果没有跳转,需要单独安装 kubernetes-dashboard3.2.1、方式一:一步到位3.2.2、方式二:逐步进行 1、Enab…...
信息学奥赛一本通 2087:【22CSPJ普及组】解密(decode) | 洛谷 P8814 [CSP-J 2022] 解密
【题目链接】 洛谷 P8814 [CSP-J 2022] 解密 ybt 2087:【22CSPJ普及组】解密(decode) 【题目考点】 1. 数学:一元二次方程求根 【解题思路】 输入n,d,e,满足 n p ∗ q np*q np∗q e ∗ d ( p − 1 ) ( q − 1…...
【重学 MySQL】四十八、DCL 中的 commit 和 rollback
【重学 MySQL】四十八、DCL 中的 commit 和 rollback commit的定义与作用rollback的定义与作用使用场景相关示例注意事项DDL 和 DML 的说明 在MySQL中,DCL(Data Control Language,数据控制语言)用于管理数据库用户和控制数据的访问…...
Java面试八股之认证授权
一、概念: 1、什么是认证?什么是授权? 认证 用于在系统登录时,验证身份的凭证,类似于账号、密码等。 授权 用户在访问资源时,根据权限的不同对资源访问程度不同。 2、什么是cookie?什么是…...
RCE_绕过综合
<aside> 💡 管道符 </aside> <aside> 💡 通配符绕过 </aside> **匹配任何字符串/文本,包括空字符串;*代表任意字符(0个或多个)? 匹配任何一个字符(不…...
关于Generator,async 和 await的介绍
在本篇文章中我们主要围绕下面几个问题来介绍async 和await 🍰Generator的作用,async 及 await 的特点,它们的优点和缺点分别是什么?await 原理是什么? 📅我的感受是我们先来了解Generator,在去…...
Redis数据库与GO(二):list,set
一、list(列表) list(列表)是简单的字符串列表,按照插入顺序排序。你可以添加一个元素到列表的头部(左边)或者尾部(右边)。List本质是个链表, list是一个双向链表,其元素是有序的,元…...
c++知识点总结
1.把字符串a复制到b里面 #include<iostream> #include<string.h> using namespace std; int main() {char a[110],b[110];cin>>a;int n strlen(a);for(int i 0;i<n1;i){b[i] a[i];}cout<<b;return 0; }2.比较两个字符串的大小 如果a大返回1&…...
无IDEA不Java:快速掌握Java集成开发环境
IntelliJ IDEA是一种强大的Java集成开发环境,是Java开发人员的首选工具之一。本文将介绍IDEA的基本使用方法和常用功能,以帮助初学者快速上手。 安装和配置 首先,需要下载并安装IntelliJ IDEA。在安装完成后,需要配置JDKÿ…...
9.30学习记录(补)
手撕线程池: 1.进程:进程就是运行中的程序 2.线程的最大数量取决于CPU的核数 3.创建线程 thread t1; 在使用多线程时,由于线程是由上至下走的,所以主程序要等待线程全部执行完才能结束否则就会发生报错。通过thread.join()来实现 但是如果在一个比…...
移动应用中提升用户体验的因素
用户体验(UX)是任何移动应用程序成功的关键因素。随着数以百万计的应用程序争夺注意力,提供无缝、愉快和高效的体验可能是获得忠实用户或在一次互动后失去忠实用户之间的区别。无论是商业应用程序、游戏还是社交平台,增强用户体验…...
VS与VSCode的区别
文章目录 1. 什么是 Visual Studio 和 Visual Studio Code?Visual Studio(VS)Visual Studio Code(VS Code) 2. 主要区别详解性能和资源占用功能和复杂性扩展和自定义适用场景价格 3. 详细对比总结4. 如何选择适合自己的…...
用Python和OpenCV实现人脸识别:构建智能识别系统
解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 人脸识别技术在现代社会的各个领域得到了广泛应用,从智能手机的面部解锁到公共场所的安全监控,人脸识别已经成为一项日益重要的技术。本教程将指导你使用Python中的OpenCV库来构建一个简单的人脸检测与识别系统…...
微积分-反函数6.5(指数增长和衰减)
在许多自然现象中,数量的增长或衰减与其大小成正比。例如,如果 y f ( t ) y f(t) yf(t) 表示在时间 t t t 时某种动物或细菌种群的个体数量,那么似乎可以合理地假设增长速率 f ’ ( t ) f’(t) f’(t) 与种群 f ( t ) f(t) f(t) 成正比…...
C初阶(十二)do - while循环 --- 致敬革命烈士
大家国庆看阅兵仪式和天安门升旗仪式了吗?岁月安好,只因有人负重前行。 ————山那边是什么 ————是烈士的英魄 ————是他们拼死保卫的新中国 ————河那边是什么 ————是绵延的战火 ————她望着远方泪一滴滴的落 ————和平来了 ——…...
从零开始:SpringBoot实现古典舞在线交流平台
第二章 相关技术介绍 2.1Java技术 Java是一种非常常用的编程语言,在全球编程语言排行版上总是前三。在方兴未艾的计算机技术发展历程中,Java的身影无处不在,并且拥有旺盛的生命力。Java的跨平台能力十分强大,只需一次编译…...
AL生成文章标题指定路径保存:创新工具助力内容创作高效启航
在信息爆炸的时代,一个吸引人的标题是文章成功的第一步。它不仅要准确概括文章内容,还要能激发读者的好奇心,促使他们点击阅读。随着人工智能技术的飞速发展,AL生成文章标题功能正逐渐成为内容创作者的新宠,看看它是如…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...
