組合數計算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-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);
}

三：用線性求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;
}