组合数计算的几种方法

喜欢ヅ旅行 2022-10-27 15:57 366阅读 0赞

# 组合数计算的几种方法 #

## 方法一、公式法(此方法适合n和m都很小时使用) ##

**公式:C(n,m)=C(n-1,m)+C(n-1,m-1)**  
我们在进行计算时可以采用动态规划的方法  
代码描述:

static long C(int n,int m) {
        
    		long[] res=new long[m+1];
    		Arrays.fill(res, 1);
    		for(int i=0;i<=n;i++) {
        
    			for(int j=Math.min(i, m);j>=0;j--) {
        
    				if(j==0 || i==j) {
        
    					res[j]=1;
    					continue;
    				}
    				res[j]=res[j]+res[j-1];
    			}
    		}
    		return res[m];
    	}

## 方法二、利用乘法逆元(此方法适合对组合数求模时候使用) ##

对于乘法逆元不了解的需要自行百度，我们在此之说目的，引入乘法逆元是为了使得(a/b)%p转化为(a\*inv(b))%p，即将除法求模转换为乘法求模，对于逆元的求解本人比较喜欢用费马小定理，其要求是gcd(b,p)==1 && p为质数，在这种情况下inv(b)=pow(b,p-2,p)。  
代码描述:

//组合数快速计算 
    	static long C(int n,int m) {
        
    		if(m<0 || n<m) return -1;  //不存在
    		if(m>n-m) m=n-m;          //转换为小的一部分
    		long up=1,lo=1;
    		for(int i=0;i<m;i++) {
        
    			up=(up*(n-i))%p;
    			lo=(lo*(i+1))%p;
    		}
    		return (up*inv((int)lo,p))%p;
    	}
    	
    	static int inv(int a,int p) {
        
    		return quickPow(a,p-2,p);
    		//另一种求逆元的方法
    		//return (int)(long)(p-p/a)*inv(p%a,p)%p;
    	}
    	
    	static int quickPow(int a,int b,int mod) {
        
    		long x=a % mod;
    		long res=1;
    		while(b!=0) {
        
    			if((b&1)==1) res=(res*x)%mod;
    			x=(x*x)%mod;
    			b>>=1;
    		}
    		return (int)res;
    	}

发表评论取消回复

表情：

评论列表（有 0 条评论，366人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python执行时间的几种计算方法

更多编程教程请到：[菜鸟教程][Link 1] https://www.piaodoo.com/ 友情链接：[好看站][Link 2] http://www.nrso.net

怼烎@/ 2022年12月20日 11:13/ 0 赞/ 185 阅读

相关计算组合数

编写函数，参数是两个非负整数n和m，返回组合数Cmn=n!/(m!(n-m)!),其中m<=n<=25。例如，n=25,m=12时答案为5200300。 //有问题

旧城等待，/ 2022年11月25日 13:30/ 0 赞/ 171 阅读

相关计算组合数

include<stdio.h> / 函数原型 / long Fact(int x); long Comb(int m, int k);

Bertha 。/ 2022年11月14日 13:23/ 0 赞/ 129 阅读

相关组合数计算的几种方法

组合数计算的几种方法方法一、公式法(此方法适合n和m都很小时使用) 公式:C(n,m)=C(n-1,m)+C(n-1,m-1) 我们在进行计算时可以采用动态规

喜欢ヅ旅行/ 2022年10月27日 15:57/ 0 赞/ 367 阅读

相关计算组合数

计算组合数 Time Limit: 1000ms Memory limit: 32768K 有疑问？点这里^\_^ 题目描述计算组合数。C(n,m),表示从

左手的ㄟ右手/ 2022年08月10日 04:59/ 0 赞/ 152 阅读

相关组合数的计算

组合数的计算 Time Limit: 2000ms Memory limit: 32768K 有疑问？点这里^\_^ 题目描述给定n组整数(a,b)，计算组

太过爱你忘了你带给我的痛/ 2022年08月10日 04:58/ 0 赞/ 167 阅读

相关计算组合数

Problem Description 计算组合数。C(n,m),表示从n个数中选择m个的组合数。计算公式如下：若：m=0，C(n,m)=1 否则，若

女爷i/ 2022年07月14日 15:23/ 0 赞/ 157 阅读

相关计算组合数

Problem Description 计算组合数。C(n,m),表示从n个数中选择m个的组合数。计算公式如下：若：m=0，C(n,m)=1 否

矫情吗；*/ 2022年06月11日 03:23/ 0 赞/ 180 阅读

相关组合数的几种求法

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpe

Bertha 。/ 2022年03月18日 18:12/ 0 赞/ 246 阅读

相关乘法逆元的几种计算方法

转载自：[https://blog.csdn.net/rain722/article/details/53170288][https_blog.csdn.net_rain722

Bertha 。/ 2022年03月10日 13:28/ 0 赞/ 317 阅读