组合数(Combinatorial_Number)_组合数的写法-程序员宅基地

技术标签: 算法  C++  # 算法  # 经典问题  # C++  组合数  数学  

定义:

从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合;从n个不同元素中取出m(m≤n)个元素的所有组合的个数,叫做从n个不同元素中取出m个元素的组合数。

公式:

在线性写法中被写作C(m,n)。

c(m,n)=p(m,n)/n!=m!/((m-n)!*n!)

性质:

1.互补性质

组合数性质如右图所示:

即从m个不同元素中取出n个元素的组合数=从m个不同元素中取出(m-n)个元素的组合数组合数性质

这个性质很容易理解,例如C(9,2)=C(9,7),即从9个元素里选择2个元素的方法与从9个元素里选择7个元素的方法是相等的。

规定:C(m,0)=1

2.组合恒等式

若表示在n个物品中选取m个物品,则如存在下述公式: C(n,m)= C(n,n-m)= C(n-1,m-1)+C(n-1,m)

求法:

1、一般方法

直接套公式:

组合数性质

求出m!、n!、(m-n)!然后带人公式;

代码如下:

# include<stdio.h>
# include<math.h>
int f(int n){
	int i,m=1;
	for(i=1;i<=n;i++){
		m=m*i;
        }
	return m;
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	printf("%d\n",f(n)/(f(m)*f(n-m)));
	return 0;
}

稍微用点小技巧

long long C(int n,int m)
{
    if(m<n-m)    m=n-m;
    long long ans=1;
    for(int i=m+1;i<=n;++i)    ans*=i;
    for(int i=1;i<=n-m;++i)    ans/=i;
    return ans;
}

 

2、杨辉三角

就算是long long最多20!左右;再大就会爆了

那就用到我们大数学家杨辉的三角了

: C(n,m)= C(n,n-m)= C(n-1,m-1)+C(n-1,m)

#include<iostream>
using namespace std;
long long c[100][100];
inline void get_it(int n)
{
        c[0][0]=1;
        for (int i=1;i<=n;i++)
                for (int j=0;j<=i;j++)
                        if (i==j ||j==0) c[i][j]=1;
                        else c[i][j]=c[i-1][j]+c[i-1][j-1];
}
int main()
{
        get_it(60);
        for (int i=1;i<=60;i++)
                {for (int j=1;j<=i;j++)
                cout<<c[i][j]<<" ";
        cout<<endl;}
}

理论上只要数组开的出来都可以,最多,emmm,反正比一般方法强。 

3、快速组合数

这个要用快速幂:https://blog.csdn.net/weixin_43272781/article/details/85058595

主要是用在一般方法;求阶乘的时候。

我就不写了。

4、求余组合数

以上方法最多也就到long long的极限,当然超过long long的我们也存储不下了,但是如果我们只需要一部分高阶组合数,用杨辉三角太浪费了吧。而且一般题目会有求余的要求,那么接下来就是大招了。

证明:https://blog.csdn.net/arrowlll/article/details/52629448

 1).扩展欧几里德:b*x+p*y=1 有解,x就是所求

 2).费马小定理:b^(p-1)=1(mod p),故b*b^(p-2)=1(mod p),所以x=b^(p-2)



1. n!/(m!*(n-m)! =x%p ,先对算出n!、m!、(n-m)!对p取模的余数,就转换为a/b=x%p;因为p为素数,所以等价于bx+py=a;然后用扩展的欧几里得定理算出 bx’+py’=1的解,x=x’*a,就得到了最终的x的值,即C(m,n)%p得值。

2.逆元 其实如果mod是素数 则b的逆元其实就是b^(mod-2) 
也就是 (m!(n-m)!)的逆元为 (m!(n-m)!)p-2 ;

int inv(int a) {  
    //return fpow(a, MOD-2, MOD);  
    return a == 1 ? 1 : (long long)(MOD - MOD / a) * inv(MOD % a) % MOD;  
}  
LL C(LL n,LL m)  
{  
    if(m < 0)return 0;  
    if(n < m)return 0;  
    if(m > n-m) m = n-m;  

    LL up = 1, down = 1;  
    for(LL i = 0 ; i < m ; i ++){  
        up = up * (n-i) % MOD;  
        down = down * (i+1) % MOD;  
    }  
    return up * inv(down) % MOD;  
}  



3.当n和m比较大,mod是素数且比较小的时候(10^5左右),通过Lucas定理计算

Lucas定理:A、B是非负整数,p是质数。A B写成p进制:A=a[n]a[n-1]…a[0],B=b[n]b[n-1]…b[0]。 
则组合数C(A,B)与C(a[n],b[n])C(a[n-1],b[n-1])…*C(a[0],b[0]) mod p同余 
即:Lucas(n,m,p)=C(n%p,m%p)*Lucas(n/p,m/p,p)

#include<iostream>
//#include<algorithm>
using namespace std;
typedef long long ll;
int quick_power_mod(int a,int b,int m){//pow(a,b)%m
    int result = 1;
    int base = a;
    while(b>0){
         if(b & 1==1){
            result = (result*base) % m;
         }
         base = (base*base) %m;
         b>>=1;
    }
    return result;
}
//计算组合数取模
ll comp(ll a, ll b, int p) {//composite num C(a,b)%p
    if(a < b)   return 0;
    if(a == b)  return 1;
    if(b > a - b)   b = a - b;

    int ans = 1, ca = 1, cb = 1;
    for(ll i = 0; i < b; ++i) {
        ca = (ca * (a - i))%p;
        cb = (cb * (b - i))%p;
    }
    ans = (ca*quick_power_mod(cb, p - 2, p)) % p;
    return ans;
}
ll lucas(ll n, ll m, ll p) {
     ll ans = 1;

     while(n&&m&&ans) {
        ans = (ans*comp(n%p, m%p, p)) % p;//also can be recusive
        n /= p;
        m /= p;
     }
     return ans;
}
int main(){
    ll m,n;
    while(cin>>n>>m){
        cout<<lucas(n,m,10007)<<endl;
    }
    return 0;
}


C(n % mod, m % mod) % mod; 如果太大还是利用上面的逆元来处理。

半预处理 
由于Lucas定理保证了阶乘的数均小于p,所以可以讲所有的阶乘先预处理,优化C(n,m) 
mod的要求:p<10^6,且为素数 
有效范围:1<=n,m<=10^9

//半预处理  
const ll MAXN = 100000;  
ll fac[MAXN+100];  
void init(int mod)  
{  
    fac[0] = 1;  
    for (int i=1; i<mod; i++){  
        fac[i] = fac[i-1] * i % mod;  
    }  
}  

//半预处理逆元求C(n,m)%mod  
ll C(ll n, ll m)  
{  
    if ( m>n ) return 0;  
    return fac[n] * (GetInverse(fac[m]*fac[n-m], mod)) % mod;  
}  


typedef long long LL;
const LL maxn(1000005), mod(1e9 + 7);
LL Jc[maxn];

void calJc()    //求maxn以内的数的阶乘
{
    Jc[0] = Jc[1] = 1;
    for(LL i = 2; i < maxn; i++)
        Jc[i] = Jc[i - 1] * i % mod;
}
/*
//拓展欧几里得算法求逆元
void exgcd(LL a, LL b, LL &x, LL &y)    //拓展欧几里得算法
{
    if(!b) x = 1, y = 0;
    else
    {
        exgcd(b, a % b, y, x);
        y -= x * (a / b);
    }
}

LL niYuan(LL a, LL b)   //求a对b取模的逆元
{
    LL x, y;
    exgcd(a, b, x, y);
    return (x + b) % b;
}
*/

//费马小定理求逆元
LL pow(LL a, LL n, LL p)    //快速幂 a^n % p
{
    LL ans = 1;
    while(n)
    {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}

LL niYuan(LL a, LL b)   //费马小定理求逆元
{
    return pow(a, b - 2, b);
}

LL C(LL a, LL b)    //计算C(a, b)
{
    return Jc[a] * niYuan(Jc[b], mod) % mod
        * niYuan(Jc[a - b], mod) % mod;
}

例题

https://blog.csdn.net/weixin_43272781/article/details/85269419

 

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_43272781/article/details/85311412

智能推荐

北斗导航 | 北斗三号之RDSS短报文之双向零值-程序员宅基地

文章浏览阅读2.4k次。================================================博主github:https://github.com/MichaelBeechan博主CSDN:https://blog.csdn.net/u011344545================================================影响卫星无线电测定业务接收机工作性能的指标有很多,其中对测距精度有影响的主要是接收机的双向零值。RDSS工作原理参考:北斗导航 | 北斗RD_双向零值

Unity3d通过PhotonServer访问MySQL数据库_unity photon engine数据库-程序员宅基地

文章浏览阅读2.7k次,点赞6次,收藏11次。接着上一篇文章内容继续开发上一片篇文章介绍到NHibernate与数据库交互_unity photon engine数据库

ubuntu18.04开机后鼠标键盘失灵问题_ubuntu18.04开机鼠标键盘没反应-程序员宅基地

文章浏览阅读3.9k次,点赞4次,收藏12次。环境:Ubuntu 18.04 + Windows 10 双系统重启系统后按“ESC”进入grub引导界面:这里看个人电脑情况,楼主按一下“ESC”就可以进入了。在引导界面选择 Advanced Options选择 带有(Recovery mode )的选项接着选择 Network 并点 yes继续选择 Drop to root shell prompt,并点“En..._ubuntu18.04开机鼠标键盘没反应

matlab eps-程序员宅基地

文章浏览阅读40次。matlabepseps是一个函数。当没有参数时默认参数是1.返回的是该参数的精度。也就是说单个的eps实际上是eps(1),表示的是1的精度。这里要说一下精度的概念。浮点数所能表示的数值范围是很大的,但是浮点数不是无限的,连续的和稠密的;而是有限的,离散的和稀疏的,而且每个数的精度都不一样。越是靠近0,精度越高,反之则越低。eps返回的是1的精度。指的..._matlabepswin = round (1.6 * hz);

QT Creator 两种创建项目的方法_qt creator6.2创建项目-程序员宅基地

文章浏览阅读1.1w次。原文链接 http://my.oschina.net/jamesju/blog/106561最近要搞一个项目,开发的IDE是QT,完全没基础啊,各种自己学啊,各种摸索啊,于是写点儿基本入门的教程,看着也方便。一、打开QT Creator:双击桌面上的快捷方式,也可以通过开始->所有程序里面打开二、开始:文件->新建项目或工程_qt creator6.2创建项目

关于org.apache.catalina.session.StandardManager doLoad异常-程序员宅基地

文章浏览阅读162次。关于org.apache.catalina.session.StandardManager doLoad错误的解决在开发项目的时候,偶尔遇到了如下问题,在启动tomcat时抛出下列异常严重: IOException while loading persisted sessions: java.io.EOFExceptionjava.io.EOFException?at java.io.Ob..._org.apache.catalina.session.standardmanager.startinternal exception loading

随便推点

《视觉SLAM十四讲课后作业》第二讲-程序员宅基地

文章浏览阅读601次。1.设线性⽅程 Ax = b,在 A 为⽅阵的前提下,请回答以下问题:1. 在什么条件下,x 有解且唯⼀?非齐次线性方程在A的秩与[A|B]的秩相同时方程有解,当R(A)=R(A,B)=n时方程有唯一解。2. ⾼斯消元法的原理是什么?原理:高斯消元法的作用是又来求解线性方程组的解,其原理是将方程组进行加减消元,然后求出未知数X。3. QR 分解的原理是什么?原理..._视觉slam十四讲 第三讲 课后作业 判断是否为群

React 三种通信方式(父传子、子传父、兄弟传值)_react父传子-程序员宅基地

文章浏览阅读4k次。react有三种通信方式:一、父传子,二、字传父,三、兄弟之间传值一、父组件向子组件传值父组件通过属性的方式传递参数,子组件通过props来接收父组件传递过来的参数React中是单向数据流,数据只能从父组件通过属性的方式传给其子组件,如下图:在引用子组件的时候传递,相当于一个属性,例如:在子组件内通过porps.param获取到这个param的值。父组件向子组件传值,通过props,将父组件的state传递给了子组件。父组件(直接定义一个属性传值即可):imp.._react父传子

struts059-cve_2019_0230漏洞复现_cve-2019-0230-程序员宅基地

文章浏览阅读1.5k次。struts059-cve_2019_0230漏洞复现漏洞概述:该漏洞编号为CVE-2019-0230,漏洞等级:高危。攻击者可以通过构造恶意的OGNL表达式,并将其设置到可被外部输入进行修改,且会执行OGNL表达式的Struts2标签的属性值,引发OGNL表达式解析,最终造成远程代码执行的影响。复现漏洞:启动虚拟机,在docker中运行vulfocus镜像,通过浏览器访问,并下载struts059-cve_2019_0230镜像启动漏洞环境,开始漏洞复现打开漏洞.._cve-2019-0230

ElementUI使用timePicker时默认值default-value问题以及选择范围select-options问题_el-time-picker default-value-程序员宅基地

文章浏览阅读1.6w次。在时间选择器使用时,因为ElementUI官方默认选择器打开时的默认时间是当前时间,当我们需要手动设置一点击该选择器展现的默认时间时,官方也提供了dafault-value属性,如下图:该值绑定的是一个Date对象可被解析,所以我们可以默认绑定属性,通过在VUE渲染完成时给该属性赋值,这样就可以解决打开timePicker时自定义默认值的问题。// 1.在data中定义属性data{ defalutValue: null}// 2.将该属性绑定到对应的timePicker上&l._el-time-picker default-value

财经法规复习三-2-程序员宅基地

文章浏览阅读36次。财经法规复习三-2 44、一般存款账户,是指存款人因借款或其他结算需要,在基本存款账户开户银行内其他营业机构开立的银行结算账户。( )Y、对N、错44、正确答案:N解析:本题考核一般存款账户的概念。一般存款账户,是指存款人因借款或其他结算需要,在基本存款账户开户银行以外的银行营业机构开立的银行结算账户。50、所有记账凭证必须...

电力负荷预测 | 电力系统负荷预测模型(Python线性回归、随机森林、支持向量机、BP神经网络、GRU、LSTM)-程序员宅基地

文章浏览阅读1.5k次,点赞3次,收藏2次。电力负荷预测 | 电力系统负荷预测模型(Python线性回归、随机森林、支持向量机、BP神经网络、GRU、LSTM)

推荐文章

热门文章

相关标签