本文共 1887 字，大约阅读时间需要 6 分钟。

组合数

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

公    式：C(n,m)=n!/((n-m)!*m!)（m≤n）

性质1：C(n,m)= C(n,n-m)

性质2：C(n,m)=C(n-1,m-1)+C(n-1,m)

定义 组合是数学的重要概念之一。从 n 个不同元素中每次取出 m 个不同元素

，不管其顺序合成一组，称为从 n 个元素中不重复地选取 m 个元素的一个组合。所有这样的组合的种数称为组合数。

性质

1.互补性质

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

 

例如C(9,2)=C(9,7)，即从9个元素里选择2个元素的方法与从9个元素里选择7个元素的方法是相等的。

规定：C(n,0)=1

2.

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

 

问题

用递归法计算从n个人中选择k个人组成一个委员会的不同组合数。

由n个人里选k个人的组合数 = 由n-1个人里选k个人的组合数 + n-1个人里选k-1个人的组合数

从n-1个人增加到n个人，最后一个人可能被选中也可能不被选中，有两种情况：

1.不被选中，即需要从n-1个人中选择k个人。

2.被选中，即需要从n-1个人中选择k-1个人。 这两种情况加起来就是从n个人里选择k个人的组合数。

#include 
   
    using namespace std;// 计算从n个人里选k个人的组合数int comm(int n, int k){    if(k > n)        return 0;    else if(n == k || k == 0)        return 1;    else        return comm(n-1, k) + comm(n-1, k-1);   }int main(){    int n,k;    cout<<"Please enter two integers n and k: ";    cin>>n>>k;    cout<<"C(n, k)="<
   

卢卡斯定理（Lacus）求大组合数

现在来了新问题，如果n和m很大呢，

比如求C(n, m) % p  ， n<=1e18,m<=1e18,p<=1e5

看到没有，n和m这么大，但是p却很小，我们要利用这个p

卢卡斯说要有

C(n, m) % p  =  C(n / p, m / p) * C(n%p, m%p) % p

于是便有了大组合数有解。

找了一个大佬的理解过程：

贴个模板：

const int p=1e9+7;ll qmi(ll a,ll k)//用到快速幂/逆元/组合公式{    ll res=1;    while(k)    {        if(k&1)            res=res*a%p;        a=a*a%p;        k>>=1;    }    return res;}ll C(int a,int b){    ll res=1;    for(ll i=1,j=a;i<=b;i++,j--)    {        res=res*j%p;        res=res*qmi(i,p-2)%p;    }    return res;}ll lucas(ll a,ll b){    if(a
   

二

const int p=998244353;const int N=20000005;typedef long long ll;ll qmi(ll a,ll k,ll p){    ll res=1;    while(k)    {        if(k&1)            res=res*a%p;        a=a*a%p;        k>>=1;    }    return res;}ll fac[N];void init(){    fac[0]=1;    for(int i=1;i<=N-10;++i)        fac[i]=fac[i-1]*i%p;}ll C(ll n,ll m){    return fac[n]*qmi(fac[n-m]*fac[m]%p,p-2,p)%p;}

 

转载地址：http://evyzi.baihongyu.com/