组合数求法汇总
一:递推求解
对于组合数,有此式: 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生成文章标题功能正逐渐成为内容创作者的新宠,看看它是如…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
