组合数的几种求法

Bertha 。 2022-03-18 18:12 282阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70][]

代码：

//n方打表法 
    int Ctable(int n,int m){
    	int C[100][100];//n,m
    	for(int i=1;i<=n;i++){
    		C[1][i]=i;
    		C[i][i]=1;
    	}
    	for(int i=2;i<=n;i++){
    		for(int j=i+1;j<=n;j++){
    				C[i][j]=C[i][j-1]+C[i-1][j-1];//理解需要画图 
    		}
    	}
    	return C[m][n];
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70 1][]

### 关于ex\_gcd求逆元的原理： ###

### a\*x=1(mod)   --->    a\*x =  k\*mod  +1   --->    a\*x -k\*mod   =1   ----->   a\*x + mod\*y=1    扩展欧几里得求逆元的思路 ###

### 注意：GCD（a, mod）必须为1    否则逆元不存在      （逆元存在也可能为负，需要进行一下处理：niyuan = (x+mod)%mod） ###

int exgcd(int a,int b,int &x,int &y) {
    	if(b==0){
    		x=1;
    		y=0;
    		return a;//返回最小公倍数，如果a和b不互质的话是没有乘法逆元的； 
    	}
    	int t=exgcd(b,a%b,x,y);
    	int k=x;
    	x=y;
    	y=k-a/b*y;
    	return t;
    }
    //Nlogn打表法
    int res(int n,int m,int p){//模P意义下的组合数 
    	int k[100],ni[100];//阶乘 逆元 
    	k[1]=1;
    	for(int i=2;i<=100;i++)k[i]=i*k[i-1];//前N项的阶乘 
    	//扩展欧几里得求逆元 logn
    	for(int i=1;i<=n;i++){
    		int x,y;
    		int r=exgcd(k[i],p,x,y); 
    		if(r==1)ni[i]=(x+p)%p;
    		else ni[i]=-1;
    	} 
    	return k[n]*ni[n-m]*ni[m];//要求是 n-m ，m均和 P互质（如果不互质呢？） 
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70 2][]

[https://www.cnblogs.com/fzl194/p/9095177.html][https_www.cnblogs.com_fzl194_p_9095177.html]    （Lucas定理的使用）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70]: /images/20220318/a821039c07d745409343406c27b87e49.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70 1]: /images/20220318/cbf8026cde07473d887bc12bc4d106a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70 2]: /images/20220318/3cf30ebed224494ebae0cc0ca9d8ec0d.png
[https_www.cnblogs.com_fzl194_p_9095177.html]: https://www.cnblogs.com/fzl194/p/9095177.html