組合數(shù)：
在N個數(shù)中選取M個數(shù)，問選的方式有幾種？

直接遞歸暴力簡單

#include<cstdio> const int N = 2000 + 5; const int MOD = (int)1e9 + 7; int comb[N][N];//comb[n][m]就是C(n,m) void init(){for(int i = 0; i < N; i ++){comb[i][0] = comb[i][i] = 1;for(int j = 1; j < i; j ++){comb[i][j] = comb[i-1][j] + comb[i-1][j-1];comb[i][j] %= MOD;}} } int main(){init(); }

盧卡斯定理：
求$C_m^{n}modp$
設(shè)$m={a_0}^{p_0}+{a_1}^{p_1}+?+{a_k}^{p_k}$
設(shè)$n={b_0}^{p_0}+{b_1}^{p_1}+?+{b_k}^{p_k}$
則$C_m^n\equiv \prod C_{a_i}^{b_i}(modp)$

證明我就不打了，百度百科上有，數(shù)學符號太多了~ _ ~
前置知識：
1.歐幾里得或者費馬小定理求逆元
2.快速冪
實現(xiàn)代碼：

#include<iostream> using namespace std; typedef long long LL; const LL N=1e5+2; LL a[N]; void init(LL p) {a[1]=1;for(int i=2;i<=p;++i)a[i]=a[i-1]*i%p; } void exgcd(LL a,LL b,LL &x,LL &y) {if(!b){x=1;y=0;return;}exgcd(b,a%b,y,x);y-=a/b*x; } LL ksm(LL x,LL n,LL mod) {LL ans=1;while(n){if(n&1)ans=ans*x%mod;n>>=1;x=x*x%mod;}return ans; } LL C(LL n,LL m,LL p) {if(n==m||m==0)return 1;if(n<m)return 0;if(m*2>n)m=n-m; /*C(n,m)=c(n,n-m)*/return a[n]*ksm(a[m]*a[n-m],p-2,p)%p; /*求(a[m]*a[n-m])在(mod p)意義下的乘法逆元*//*拓展歐幾里得與費馬小定理均可*/ /*LL x,y;exgcd(a[m]*a[n-m],p,x,y);return (a[n]*x%p+p)%p;*/ } LL lucas(LL n,LL m,LL p) {if(!m)return 1;return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p; } int main() {ios::sync_with_stdio(false);LL T,n,m,p;cin>>T;while(T--){cin>>n>>m>>p;init(p);cout<<lucas(n+m,m,p)<<endl;}return 0; }

為了快，放了一個數(shù)組，限制了P的大小，然后再發(fā)一個沒有限制的盧卡斯。

#define MOD 1000000007 typedef long long LL;LL quickPower(LL a, LL b) {LL ans = 1;a %= MOD;while (b){if (b & 1){ans = ans * a % MOD;}b >>= 1;a = a * a % MOD;}return ans; }LL c(LL n, LL m) {if (m > n){return 0;}LL ans = 1;for (int i = 1; i <= m; i++){LL a = (n + i - m) % MOD;LL b = i % MOD;ans = ans * (a * quickPower(b, MOD - 2) % MOD) % MOD;}return ans; }LL lucas(LL n, LL m) {if (m == 0){return 1;}return c(n % MOD, m % MOD) * lucas(n / MOD, m / MOD) % MOD; }int main(int argc, const char * argv[]) {LL n, m;while (~scanf("%lld %lld", &n, &m)){LL max, min;max = n + m - 3;min = m - 1;printf("%lld\n", lucas(max - 1, min - 1));}return 0; }

ExLucas擴展盧卡斯定理：
求解$C_n^m\%P$,其中m,n較大，P較小且不一定為素數(shù)
轉(zhuǎn)化為CRT（中國剩余定理）
好像這也不是什么定理，只是一個計算方法

參考
$$\begin{gathered} 19! \\ =1\times 2\times 3\times ?\times 19 \\ =(1\times 2\times 4\times 5\times 7\times 8?\times 16\times 17\times 19)\times (3\times 6\times 9\times 12\times 15\times 18) \\ =(1\times 2\times 4\times 5\times 7\times 8?\times 16\times 17)\times 19\times 36\times (1\times 2\times 3\times 4\times 5\times 6) \\ =(1\times 2\times 4\times 5\times 7\times 8)2\times 19\times 36\times (1\times 2\times 3\times 4\times 5\times 6) \end{gathered}$$

上面這個式子分為四部分：

#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL N=1e5+9; LL A[N],M[N]; LL ksm(LL x,LL n,LL mod) {LL ans=1;while(n){if(n&1)ans=ans*x%mod;n>>=1,x=x*x%mod;}return ans; } void exgcd(LL a,LL b,LL &x,LL &y) {if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=a/b*x; } LL inv(LL a,LL p) {LL x,y;exgcd(a,p,x,y);return (x+p)%p?x:x+p; } LL get(LL n,LL pi,LL p) /*求(與pi互素后的n!)%M[i]*/ {if(!n)return 1;LL ans=1;if(n/p){ /*判斷有無循環(huán)節(jié) */ for(LL i=2;i<=p;++i)if(i%pi)ans=ans*i%p;ans=ksm(ans,n/p,p);}for(LL i=2;i<=n%p;++i)if(i%pi)ans=ans*i%p; /*循環(huán)節(jié)剩余部分*/ return ans*get(n/pi,pi,p)%p; } LL exlucas(LL n,LL m,LL pi,LL p) /*求A[i]*/ {LL nn=get(n,pi,p); /*求(與pi互素后的n)%M[i]*/ LL mm=get(m,pi,p); /*求(m!與pi互素后的m!)%M[i]*/ LL nm=get(n-m,pi,p); /*求(與pi互素后的(n-m)!)%M[i]*/ LL k=0; /*含質(zhì)因數(shù)pi的數(shù)量*/ for(LL i=n;i;i/=pi)k+=i/pi;for(LL i=m;i;i/=pi)k-=i/pi;for(LL i=n-m;i;i/=pi)k-=i/pi;return nn*inv(mm,p)*inv(nm,p)*ksm(pi,k,p)%p; } LL crt(LL len,LL Lcm) {LL ans=0;for(LL i=1;i<=len;++i){LL Mi=Lcm/M[i];ans=((ans+A[i]*inv(Mi,M[i])*Mi)%Lcm+Lcm)%Lcm;}return ans; } int main() {ios::sync_with_stdio(false);LL n,m,P,num;while(cin>>n>>m>>P){if(n<m){cout<<0<<endl;continue;}num=0;memset(A,0,sizeof(A));memset(M,0,sizeof(M));for(LL x=P,i=2;i<=P;++i)if(x%i==0){M[++num]=1;while(x%i==0){M[num]*=i;x/=i;}A[num]=exlucas(n,m,i,M[num])%P;} cout<<crt(num,P)<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的『数学』--数论--组合数+卢卡斯定理+扩展卢卡斯定理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。