首页 > 代码库 > 组合数计算C(n,m)加取模情况

组合数计算C(n,m)加取模情况

想法:以前做比赛的时候遇到很多需要计算组合数的情况,都是当时手敲的,写递归不是暴就是超时啥的,或者是因为要取模,然后还要求逆元,所以敲得不是慢就是老是出问题,所以现在搞出模板来以后用就快了。

一:线性求C(n,m)

解释:由HDU 4927这道题求的组合数,可以了解到组合数的一些递推快速求法,因为这道题就是卡组合数的时间的。如果我们要算C(10,4),我们可以先算C(10,1),再算C(10,2),再算C(10,3),再算C(10,4)。为什么我要这么求呢?

因为:C(10,1)=10/1,然后C(10,1)*9/2就等于C(10,2)了,即C(10,2)=10*9/(2*1);然后C(10,2)*8/3就等于C(10,3)了,即C(10,3)=10*9*8/(3*2*1);然后C(10,3)*7/4就等于C(10,4)了,即C(10,4)=10*9*8*7/(4*3*2*1)。刚开始我还担心分子除以分母的时候可能会不得整除呢,但是放心,已经证明过了,可以这样递推的计算,得到的每个组合肯定是对的,不会出现小数点的情况。

所以根据这个性质或者说规律,可以用代码线性的求出C(n,m)了:

ll combine1(ll n,ll m) //计算组合数C(n,m)
{
    ll sum=1; //线性计算
    for(ll i=1,j=n;i<=m;i++,j--)
        sum=sum*j/i;
    return sum;
}


二:递归求C(n,m)

c(n,m)=c(n-1,m-1)+c(n-1,m),我们可以轻易的用代码递归得出C(n,m)的值:

ll combine2(ll n,ll m) //计算组合数C(n,m)
{
    if(n==m||!m) return 1;//递归计算
    return combine2(n-1,m)+combine2(n-1,m-1);
}
两种比较:线性的求组合数是很快的,每次只从1求到m即可;但是递归就不行了,计算C(50,25)的时候已经严重超时并暴了,等了好久都得不出答案,所以以后和线性的代码吧!

三:用线性求C(n,m)%mod

void extend_gcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if(!b) d=a,x=1,y=0;
    else
    {
        extend_gcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
ll Mod(ll a,ll b,ll mod)//算出的逆元不对,明天检查一下才行
{
    if(!b) return 1;
    ll ans=Mod(a,b>>1,mod);
    ans=ans*ans%mod;
    if(b&1) ans=ans*a%mod;
    return ans;
}
ll inv(ll a,ll mod)//计算a对mod的逆元
{

    ll d,x,y;
    extend_gcd(a,mod,d,x,y);
    return d==1?(x+mod)%mod:-1;
    //return Mod(a,mod-2,mod);
}
ll combine1(ll n,ll m,ll mod)//计算组合C(n,m)%mod
{
    ll sum=1; //线性计算
    for(ll i=1,j=n; i<=m; i++,j--)
        sum=sum*j*inv(i,mod)%mod;
    return sum;
}