組合數(shù) 取模就是求 的值，根據(jù) ， 和 的取值范圍不同，采取的方法也不一樣。

下面，我們來(lái)看常見的兩種取值情況（m、n在64位整數(shù)型范圍內(nèi)）

（1） ? ，

???? 此時(shí)較簡(jiǎn)單，在O(n ² )可承受的情況下組合數(shù)的計(jì)算可以直接用楊輝三角遞推，邊做加法邊取模。

（2） ， ? ，并且 是素?cái)?shù)

?　 本文針對(duì)該取值范圍較大又不太大的情況（2）進(jìn)行討論。

???? 這個(gè)問題可以使用 Lucas 定理，定理描述：

　其中

????

???? ^{這樣將組合數(shù)的求解分解為小問題的乘積，下面考慮計(jì)算 C(ni, mi) %p .}

^{已知C(n, m) mod p = n!/(m!(n - m)!) mod p。當(dāng)我們要求（a/b）mod p的值，且a很大，無(wú)法直接求得a/b的值時(shí)，我們可以轉(zhuǎn)而使用乘法逆元k，將a乘上k再模p，即(a*k) mod p。 其結(jié)果與(a/b) mod p等價(jià)。}

^{那么逆元是什么？}

    
      定義：滿足a*k≡1 (mod p)的k值就是a關(guān)于p的乘法
      
        逆元
      
      （當(dāng)p是1時(shí)，對(duì)于任意a，k都為1）
    
  

^{除法取模，這里要用到m!(n-m)!的逆元。}

根據(jù) 費(fèi)馬小定理 ：

已知gcd(a, p) = 1，則 a ^p-1 ?≡ 1 (mod p), ?所以 a*a ^p-2 ?≡ 1 (mod p)。

也就是 (m!(n-m)!)的逆元為 (m!(n-m)!) ^{p-2 ；}

下面附上Lucas定理的一種證明，見下圖，參考馮志剛《 初等數(shù)論 》第37頁(yè)。

題意： 求 ，其中 ，并且 是素?cái)?shù)。

代碼：

? 上面的代碼中用到了求冪取模操作來(lái)計(jì)算(m!(n-m)!) ^p-2 % p.下面解釋冪取模算法：

反復(fù)平方法 求a ^b %m

通過研究指數(shù)b的二進(jìn)制表示發(fā)現(xiàn)，對(duì)任意的整數(shù)b都可表示為：

• n表示b的實(shí)際二進(jìn)制位數(shù)
• b _i 表示該位是0或1

因此，a ^b 可表示為：

即用b的每一位表示a的每一項(xiàng)，而對(duì)任意相鄰的兩項(xiàng)存在平方關(guān)系，即：

因此我們構(gòu)造下面的算法：

• 把b轉(zhuǎn)換為二進(jìn)制表示，并從右至左掃描其每一位（從低到高）
• 當(dāng)掃描到第i位時(shí)，根據(jù)同余性質(zhì)（2）計(jì)算a的第i項(xiàng)的模：
  
  base變量表示第i-1位時(shí)計(jì)算出的模，通過遞歸能很容易地確定所有位的模。
  
• 如果第i位為1，即b _i =1,則表示該位需要參與模運(yùn)算，計(jì)算結(jié)果 result = (result*base) mod m;其中result為前i-1次的計(jì)算結(jié)果；若b _i =0，則表示a的第i項(xiàng)為1，不必參與模運(yùn)算

    
      int quick_power_mod(int a,int b,int 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;

}
    
  

其中運(yùn)用了兩個(gè)同余性質(zhì)：

同余性質(zhì)1：ab≡bc (mod m)

同余性質(zhì)2： ? a≡c (mod m) => a ² ≡c ² (mod m)

理解要點(diǎn)：

• base記錄了a的每項(xiàng)的模，無(wú)論b在該位是0還是1，該結(jié)果都記錄，目的是給后續(xù)位為1的項(xiàng)使用，計(jì)算方式是前一結(jié)果的平方取模，這也是反復(fù)平方法的由來(lái)
• result只記錄了位為1的項(xiàng)的模結(jié)果，該計(jì)算方式使用了同余性質(zhì)1
• 通過地把a(bǔ)使用二進(jìn)制表示，并結(jié)合同余性質(zhì)1，2，巧妙地化解了大數(shù)取模的運(yùn)算。對(duì)1024位這樣的大數(shù)，也最多進(jìn)行1024次循環(huán)便可計(jì)算模值，性能非常快。

該方法是許多西方數(shù)學(xué)家努力的結(jié)果，通常也稱為Montgomery算法。

（以上部分內(nèi)容由網(wǎng)絡(luò)搜集整理而來(lái)，不當(dāng)之處，煩請(qǐng)不吝賜教）

?

組合數(shù)取模Lucas定理及快速冪取模