当前位置: 首页 > news >正文

组合数求法汇总

一:递推求解

对于组合数,有此式: 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=Cn1m1+Cn1m

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} Cn1m1 C n − 1 m C_{n-1}^{m} Cn1m 的方案,根据加法原理,令它们相加就得到了 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!(nm)!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) CnmCnmodpmmodpCn/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 小朋友的球:
(斯特林数,如果不知道的话很难推出来,可以学一学)

相关文章:

组合数求法汇总

一&#xff1a;递推求解 对于组合数&#xff0c;有此式&#xff1a; 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 个&#xff0c;不同的方案。对于第 n n n 个…...

Python知识点:在Python编程中,如何使用Joblib进行并行计算

开篇&#xff0c;先说一个好消息&#xff0c;截止到2025年1月1日前&#xff0c;翻到文末找到我&#xff0c;赠送定制版的开题报告和任务书&#xff0c;先到先得&#xff01;过期不候&#xff01; Joblib是一个Python库&#xff0c;它被设计用来提供轻便的并行计算解决方案&…...

matlab-对比两张图片的CIElab分量的差值并形成直方图

%对比两张图片的CIElab分量的差值并形成直方图&#xff0c;改个路径就能用&#xff0c;图片分辨率要一致 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、如果启动成功&#xff0c;可以在浏览器访问3.2、如果没有跳转&#xff0c;需要单独安装 kubernetes-dashboard3.2.1、方式一&#xff1a;一步到位3.2.2、方式二&#xff1a;逐步进行 1、Enab…...

信息学奥赛一本通 2087:【22CSPJ普及组】解密(decode) | 洛谷 P8814 [CSP-J 2022] 解密

【题目链接】 洛谷 P8814 [CSP-J 2022] 解密 ybt 2087&#xff1a;【22CSPJ普及组】解密(decode) 【题目考点】 1. 数学&#xff1a;一元二次方程求根 【解题思路】 输入n&#xff0c;d&#xff0c;e&#xff0c;满足 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中&#xff0c;DCL&#xff08;Data Control Language&#xff0c;数据控制语言&#xff09;用于管理数据库用户和控制数据的访问…...

Java面试八股之认证授权

一、概念&#xff1a; 1、什么是认证&#xff1f;什么是授权&#xff1f; 认证 用于在系统登录时&#xff0c;验证身份的凭证&#xff0c;类似于账号、密码等。 授权 用户在访问资源时&#xff0c;根据权限的不同对资源访问程度不同。 2、什么是cookie&#xff1f;什么是…...

RCE_绕过综合

<aside> &#x1f4a1; 管道符 </aside> <aside> &#x1f4a1; 通配符绕过 </aside> **匹配任何字符串&#xff0f;文本&#xff0c;包括空字符串&#xff1b;*代表任意字符&#xff08;0个或多个&#xff09;? 匹配任何一个字符&#xff08;不…...

关于Generator,async 和 await的介绍

在本篇文章中我们主要围绕下面几个问题来介绍async 和await &#x1f370;Generator的作用&#xff0c;async 及 await 的特点&#xff0c;它们的优点和缺点分别是什么&#xff1f;await 原理是什么&#xff1f; &#x1f4c5;我的感受是我们先来了解Generator&#xff0c;在去…...

Redis数据库与GO(二):list,set

一、list&#xff08;列表&#xff09; list&#xff08;列表&#xff09;是简单的字符串列表&#xff0c;按照插入顺序排序。你可以添加一个元素到列表的头部(左边)或者尾部(右边)。List本质是个链表&#xff0c; list是一个双向链表&#xff0c;其元素是有序的&#xff0c;元…...

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集成开发环境&#xff0c;是Java开发人员的首选工具之一。本文将介绍IDEA的基本使用方法和常用功能&#xff0c;以帮助初学者快速上手。 安装和配置 首先&#xff0c;需要下载并安装IntelliJ IDEA。在安装完成后&#xff0c;需要配置JDK&#xff…...

9.30学习记录(补)

手撕线程池: 1.进程:进程就是运行中的程序 2.线程的最大数量取决于CPU的核数 3.创建线程 thread t1; 在使用多线程时&#xff0c;由于线程是由上至下走的&#xff0c;所以主程序要等待线程全部执行完才能结束否则就会发生报错。通过thread.join()来实现 但是如果在一个比…...

移动应用中提升用户体验的因素

用户体验&#xff08;UX&#xff09;是任何移动应用程序成功的关键因素。随着数以百万计的应用程序争夺注意力&#xff0c;提供无缝、愉快和高效的体验可能是获得忠实用户或在一次互动后失去忠实用户之间的区别。无论是商业应用程序、游戏还是社交平台&#xff0c;增强用户体验…...

VS与VSCode的区别

文章目录 1. 什么是 Visual Studio 和 Visual Studio Code&#xff1f;Visual Studio&#xff08;VS&#xff09;Visual Studio Code&#xff08;VS Code&#xff09; 2. 主要区别详解性能和资源占用功能和复杂性扩展和自定义适用场景价格 3. 详细对比总结4. 如何选择适合自己的…...

用Python和OpenCV实现人脸识别:构建智能识别系统

解锁Python编程的无限可能:《奇妙的Python》带你漫游代码世界 人脸识别技术在现代社会的各个领域得到了广泛应用,从智能手机的面部解锁到公共场所的安全监控,人脸识别已经成为一项日益重要的技术。本教程将指导你使用Python中的OpenCV库来构建一个简单的人脸检测与识别系统…...

微积分-反函数6.5(指数增长和衰减)

在许多自然现象中&#xff0c;数量的增长或衰减与其大小成正比。例如&#xff0c;如果 y f ( t ) y f(t) yf(t) 表示在时间 t t t 时某种动物或细菌种群的个体数量&#xff0c;那么似乎可以合理地假设增长速率 f ’ ( t ) f’(t) f’(t) 与种群 f ( t ) f(t) f(t) 成正比…...

C初阶(十二)do - while循环 --- 致敬革命烈士

大家国庆看阅兵仪式和天安门升旗仪式了吗&#xff1f;岁月安好&#xff0c;只因有人负重前行。 ————山那边是什么 ————是烈士的英魄 ————是他们拼死保卫的新中国 ————河那边是什么 ————是绵延的战火 ————她望着远方泪一滴滴的落 ————和平来了 ——…...

从零开始:SpringBoot实现古典舞在线交流平台

第二章 相关技术介绍 2.1Java技术 Java是一种非常常用的编程语言&#xff0c;在全球编程语言排行版上总是前三。在方兴未艾的计算机技术发展历程中&#xff0c;Java的身影无处不在&#xff0c;并且拥有旺盛的生命力。Java的跨平台能力十分强大&#xff0c;只需一次编译&#xf…...

AL生成文章标题指定路径保存:创新工具助力内容创作高效启航

在信息爆炸的时代&#xff0c;一个吸引人的标题是文章成功的第一步。它不仅要准确概括文章内容&#xff0c;还要能激发读者的好奇心&#xff0c;促使他们点击阅读。随着人工智能技术的飞速发展&#xff0c;AL生成文章标题功能正逐渐成为内容创作者的新宠&#xff0c;看看它是如…...

从ILSVRC2015_VID到SOT与MOT:这个经典数据集如何影响了今天的多目标跟踪算法?

ILSVRC2015_VID&#xff1a;计算机视觉领域的"罗塞塔石碑"如何重塑目标跟踪技术 当计算机视觉领域的学者们谈起目标跟踪算法的演进史&#xff0c;2015年是个绕不开的年份。那一年&#xff0c;ImageNet大规模视觉识别挑战赛&#xff08;ILSVRC&#xff09;首次引入视频…...

Power BI视觉对象交互设计秘籍--巧用书签按钮实现动态提示

1. 为什么需要动态提示功能&#xff1f; 做数据分析报表最怕什么&#xff1f;不是数据不准&#xff0c;而是看报表的人看不懂。我见过太多这样的场景&#xff1a;精心设计的柱状图被用户误读&#xff0c;复杂的折线图被理解成完全相反的趋势。这时候你会想&#xff0c;要是有个…...

终极指南:VSCode Rainbow Fart如何通过Vue.js打造沉浸式编程体验

终极指南&#xff1a;VSCode Rainbow Fart如何通过Vue.js打造沉浸式编程体验 【免费下载链接】vscode-rainbow-fart 一个在你编程时疯狂称赞你的 VSCode 扩展插件 | An VSCode extension that keeps giving you compliment while you are coding, it will checks the keywords …...

chromedp实战:如何用JavaScript绕过iframe内容获取难题(附完整代码)

chromedp实战&#xff1a;突破iframe内容获取的JavaScript高阶技巧 在电商数据抓取和动态内容监控场景中&#xff0c;iframe始终是爬虫开发者最头疼的障碍之一。传统DOM操作方法在iframe嵌套页面面前往往束手无策&#xff0c;而chromedp提供的Evaluate系列方法则打开了新世界的…...

3步掌控数字记忆:WeChatMsg工具让你的聊天记录不再流浪

3步掌控数字记忆&#xff1a;WeChatMsg工具让你的聊天记录不再流浪 【免费下载链接】WeChatMsg 提取微信聊天记录&#xff0c;将其导出成HTML、Word、CSV文档永久保存&#xff0c;对聊天记录进行分析生成年度聊天报告 项目地址: https://gitcode.com/GitHub_Trending/we/WeCh…...

Blender 5.0 插件生态实战指南:从建模到渲染的流程效率革命

1. Blender 5.0插件生态的核心价值 如果你用过Blender&#xff0c;一定遇到过这样的场景&#xff1a;建模时反复手动倒角、UV展开时对着乱七八糟的贴图发呆、渲染时发现场景灯光怎么调都不自然。这些问题在Blender 5.0的插件生态中都能找到优雅的解决方案。 我做了10年三维设计…...

【分箱进阶篇】分箱的工程细节:从训练到部署的完整模式

基础篇参考&#xff1a;【分箱基础篇】pandas 分箱双子星&#xff1a;pd.cut 与 pd.qcut ​ 我们在基础篇讲了 pd.cut 和 pd.qcut 各自怎么用。但在实际项目里&#xff0c;分箱不是调一次函数就完事的。通常来说&#xff0c;训练集上算出来的切分点要保存下来&#xff0c;测试集…...

无人机海上搜救数据集 海上搜救人员识别 违规游泳识别 无人艇自主导航数据集 海洋安全监控及水上救援预警等场景 深度学习yolo格式地10625期

海洋目标检测数据集 README 项目概述 本数据集聚焦于海洋场景下的目标识别与安全监测任务&#xff0c;为海上搜救、智能无人艇导航及海洋环境监控等领域提供高质量标注数据&#xff0c;助力海洋视觉感知技术的落地应用。核心数据信息维度内容数据类别共5类&#xff1a;船只、浮…...

别光看论文!手把手带你复现CVPR 2025扩散模型加速新星:TinyFusion与DiG的代码实战

别光看论文&#xff01;手把手带你复现CVPR 2025扩散模型加速新星&#xff1a;TinyFusion与DiG的代码实战 如果你已经厌倦了在arXiv上收藏一堆永远打不开第二次的论文链接&#xff0c;或是被那些充满数学符号却缺少可运行代码的"理论创新"搞得头大&#xff0c;那么这…...

MT5中文增强工具多场景落地:保险条款通俗化改写与消费者理解度提升实践

MT5中文增强工具多场景落地&#xff1a;保险条款通俗化改写与消费者理解度提升实践 1. 项目概述与核心价值 MT5中文增强工具是一个基于Streamlit和阿里达摩院mT5模型构建的本地化NLP工具&#xff0c;专门针对中文文本进行语义改写和数据增强。这个工具的最大特点是能够在保持…...