盧卡斯定理:解決一類組合數取模問題
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)?
這個是單獨處理n!的情況，當然C(n,m)就是n!/(m!*(n-m)!)，每一個階乘都用上面的方法處理的話，就是Lucas定理了，注意這兒的p是素數是有必要的。
Lucas最大的數據處理能力是p在10^5左右，不能再大了，hdu 3037就是10^5級別的！
對于大組合數取模，n,m不大于10^5的話，用逆元的方法，可以解決。對于n,m大于10^5的話，那么要求p<10^5，這樣就是Lucas定理了，將n,m轉化到10^5以內解。
?
模板:
/* Lucas定理 C(n,m)%p(p為素數) C(n,m)與C(a[n],b[n])*C(a[n-1],b[n-1])*C(a[n-2],b[-2])*....*C(a[0],b[0])模p同余 a,b 是n，m在p進制下的數 有的推公式： (C(n%p,m%p,p)*Lcs(n/p,m/p,p))%p; 關鍵是求 C(n%p,m%p,p) 遞歸會很慢 for的話會爆掉 這里用一個定理：a/b%p <--> a*x%p x為b在b%p下的逆元 再來一個定理：x=b^(p-2) x為b在%p下的逆元 p為素數 然后預處理一下階乘就ok了 */ #include<iostream> #include<cstdio> #include<cstring>#define N 1001using namespace std; int f[N];int Mi(int a,int b,int p) {int res=1;while(b){if(b&1) res=res*a%p;b>>=1;a=a*a%p;}return res; }int C(int n,int m,int p) {if(m>n)return 0;return f[n]*Mi(f[m]*f[n-m],p-2,p)%p; }int Lus(int n,int m,int p) {if(m==0) return 1;return (C(n%p,m%p,p)*Lus(n/p,m/p,p))%p; }int main() {int n,m,p;scanf("%d%d%d",&n,&m,&p);f[0]=1;for(int i=1;i<=p;i++)f[i]=f[i-1]*i%p;printf("%d\n",Lus(n,m,p)); }
?
hdu3037?http://acm.hdu.edu.cn/showproblem.php?pid=3037
題目大意：求在n棵樹上摘不超過m顆豆子的方案，結果對p取模。
思路：題目可以轉換成 ?x1+x2+……+xn=m 有多少組解，m在題中可以取0~m。
利用插板法可以得出x1+x2+……+xn=m解的個數為C（n+m-1，m）；
則題目解的個數可以轉換成求 ? sum=C（n+m-1，0）+C（n+m-1，1）+C（n+m-1，2）……+C（n+m-1，m）
利用公式C（n，r）=C（n-1，r）+C（n-1，r-1） ?== > ?sum=C（n+m，m）。
就是要求C（n+m，m）%p。
#include<iostream> #include<cstdio> #include<cstring>#define N 100007using namespace std; long long f[N];long long Mi(long long a,long long b,long long p) {long long res=1;while(b){if(b&1) res=res*a%p;b>>=1;a=a*a%p;}return res; }long long C(long long n,long long m,long long p) {if(m>n)return 0;return f[n]*Mi(f[m]*f[n-m],p-2,p)%p; }long long Lcs(long long n,long long m,long long p) {if(m==0)return 1;return (C(n%p,m%p,p)*Lcs(n/p,m/p,p))%p; }int main() {long long n,m,p;long long t; cin>>t;while(t--){cin>>n>>m>>p;f[0]=1;for(long long i=1;i<=p;i++)f[i]=f[i-1]*i%p;printf("%lld\n",Lcs(n+m,m,p));}return 0; }
?
