首先給出這個Lucas定理：

A、B是非負整數，p是質數。AB寫成p進制：A=a[n]a[n-1]...a[0]，B=b[n]b[n-1]...b[0]。
則組合數C(A,B)與C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0])??modp同余

即：Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)?

這個定理的證明不是很簡單，我一直想找個很好的張明，但是，沒找到，昨天看到了一個解題報告，基本上可以說明白這個Lucas定理是怎么回事了，具體的是說：

以求解n! % p為例，把n分段，每p個一段，每一段求的結果是一樣的。但是需要單獨處理每一段的末尾p, 2p, ...，把p提取出來，會發(fā)現剩下的數正好又是(n / p)!，相當于劃歸成了一個子問題，這樣遞歸求解即可。

這個是單獨處理n!的情況，當然C(n,m)就是n!/(m!*(n-m)!)，每一個階乘都用上面的方法處理的話，就是Lucas定理了，注意這兒的p是素數是有必要的。

貼一個例題的代碼，方便以后看。

hdu 3037

將不大于m顆種子存放在n顆樹中，問有多少種存法。

首先是不大于m顆種子，我沒可以認為少于m的那些種子存放在了第n+1顆樹上，這樣的話，問題就轉化成了將m顆種子存放在n+1顆樹上的方案數。ok這個是組合數學里面的公式，亦即插板法，也就是X1+X2+X3+……+Xn+1 = m;ok，答案是C(n+m,m);

然后就是上面說的Lucas定理解決大組合數問題了

#include <iostream> #include <string.h> #include <stdio.h> using namespace std;#define N 100010long long mod_pow(int a,int n,int p) {long long ret=1;long long A=a;while(n){if (n & 1)ret=(ret*A)%p;A=(A*A)%p;n>>=1;}return ret; }long long factorial[N];void init(long long p) {factorial[0] = 1;for(int i = 1;i <= p;i++)factorial[i] = factorial[i-1]*i%p;//for(int i = 0;i < p;i++)//ni[i] = mod_pow(factorial[i],p-2,p); }long long Lucas(long long a,long long k,long long p) //求C(n,m)%p p最大為10^5。a,b可以很大！ {long long re = 1;while(a && k){long long aa = a%p;long long bb = k%p;if(aa < bb) return 0; //這個是最后的改動！re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-2,p)%p;//這兒的求逆不可先處理a /= p;k /= p;}return re; }int main() {int t;cin >> t;while(t--){long long n,m,p;cin >> n >> m >> p;init(p);cout << Lucas(n+m,m,p) << "\n";}return 0; }
//以上為前幾屆學長的lucas相關總結，在此基礎上，做了少許的修改。

總結

以上是生活随笔為你收集整理的Lucas定理及组合数取模的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。