组合数求法汇总
一:递推求解
对于组合数,有此式: 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生成文章标题功能正逐渐成为内容创作者的新宠,看看它是如…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
微服务通信安全:深入解析mTLS的原理与实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言:微服务时代的通信安全挑战 随着云原生和微服务架构的普及,服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...
