組合數
取模就是求
的值，根據
，
和
的取值范圍不同，采取的方法也不一樣。
下面，我們來看常見的兩種取值情況（m、n在64位整數型范圍內）
（1）
? ，
???? 此時較簡單，在O(n 2 )可承受的情況下組合數的計算可以直接用楊輝三角遞推，邊做加法邊取模。
（2）
， ?
，并且
是素數
? 本文針對該取值范圍較大又不太大的情況（2）進行討論。
???? 這個問題可以使用 Lucas 定理，定理描述：
其中
????
???? 這樣將組合數的求解分解為小問題的乘積，下面考慮計算 C(ni, mi) %p .
已知C(n, m) mod p = n!/(m!(n - m)!) mod p。當我們要求（a/b）mod p的值，且a很大，無法直接求得a/b的值時，我們可以轉而使用乘法逆元k，將a乘上k再模p，即(a*k) mod p。 其結果與(a/b) mod p等價。
那么逆元是什么？
定義：滿足a*k≡1 (mod p)的k值就是a關于p的乘法
逆元
（當p是1時，對于任意a，k都為1）
除法取模，這里要用到m!(n-m)!的逆元。
根據 費馬小定理 ：
已知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定理的一種證明，見下圖，參考馮志剛《 初等數論 》第37頁。
題意：
求
，其中
，并且
是素數。
代碼：
#include<iostream>
//
#include<algorithm>
using
namespace
std; typedef
long
long
ll;
int
quick_power_mod(
int
a,
int
b,
int
m){
//
pow(a,b)%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; }
//
計算組合數取模
ll comp(ll a, ll b,
int
p) {
//
composite num C(a,b)%p
if
(a < b)
return
0
;
if
(a == b)
return
1
;
if
(b > a - b) b = a -
b;
int
ans =
1
, ca =
1
, cb =
1
;
for
(ll i =
0
; i < b; ++
i) { ca
= (ca * (a - i))%
p; cb
= (cb * (b - i))%
p; } ans
= (ca*quick_power_mod(cb, p -
2
, p)) %
p;
return
ans; } ll lucas(ll n, ll m, ll p) { ll ans
=
1
;
while
(n&&m&&
ans) { ans
= (ans*comp(n%p, m%p, p)) % p;
//
also can be recusive
n /=
p; m
/=
p; }
return
ans; }
int
main(){ ll m,n;
while
(cin>>n>>
m){ cout
<<lucas(n,m,
10007
)<<
endl; }
return
0
; }
? 上面的代碼中用到了求冪取模操作來計算(m!(n-m)!) p-2 % p.下面解釋冪取模算法：
反復平方法 求a b %m
通過研究指數b的二進制表示發現，對任意的整數b都可表示為：
- n表示b的實際二進制位數
- b i 表示該位是0或1
因此，a b 可表示為：
即用b的每一位表示a的每一項，而對任意相鄰的兩項存在平方關系，即：
因此我們構造下面的算法：
- 把b轉換為二進制表示，并從右至左掃描其每一位（從低到高）
-
當掃描到第i位時，根據同余性質（2）計算a的第i項的模：
base變量表示第i-1位時計算出的模，通過遞歸能很容易地確定所有位的模。
- 如果第i位為1，即b i =1,則表示該位需要參與模運算，計算結果 result = (result*base) mod m;其中result為前i-1次的計算結果；若b i =0，則表示a的第i項為1，不必參與模運算
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;
}
其中運用了兩個同余性質：
同余性質1：ab≡bc (mod m)
同余性質2： ? a≡c (mod m) => a 2 ≡c 2 (mod m)
理解要點：
- base記錄了a的每項的模，無論b在該位是0還是1，該結果都記錄，目的是給后續位為1的項使用，計算方式是前一結果的平方取模，這也是反復平方法的由來
- result只記錄了位為1的項的模結果，該計算方式使用了同余性質1
- 通過地把a使用二進制表示，并結合同余性質1，2，巧妙地化解了大數取模的運算。對1024位這樣的大數，也最多進行1024次循環便可計算模值，性能非常快。
該方法是許多西方數學家努力的結果，通常也稱為Montgomery算法。
（以上部分內容由網絡搜集整理而來，不當之處，煩請不吝賜教）
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
