程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 組合數計算C(n,m)加取模情況

組合數計算C(n,m)加取模情況

編輯:關於C

想法:以前做比賽的時候遇到很多需要計算組合數的情況,都是當時手敲的,寫遞歸不是暴就是超時啥的,或者是因為要取模,然後還要求逆元,所以敲得不是慢就是老是出問題,所以現在搞出模板來以後用就快了。

一:線性求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;
}




  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved