hdu 3037 Saving Beans [大組合數取模-Lucas定理+逆元取模]

Lucas定理

A、B是非負整數，p是質數。A B寫成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])  mod p同余

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

//快速冪a^b % k

[cpp]  ll PowerMod(ll a, ll b, ll k) { 
    ll tmp = a, ret = 1; 
    while (b) { 
        if (b & 1) ret = ret * tmp % k; 
        tmp = tmp * tmp % k; 
        b >>= 1; 
    } 
    return ret; 
} 

ll PowerMod(ll a, ll b, ll k) {
    ll tmp = a, ret = 1;
    while (b) {
        if (b & 1) ret = ret * tmp % k;
        tmp = tmp * tmp % k;
        b >>= 1;
    }
    return ret;
}

//求C(n, m)%p   p最大為10^5    n, m可以很大！

[cpp]  ll Lucas(ll n, ll m, ll p) { 
    ll ret = 1; 
    while (n && m) { 
        ll nn = n%p, mm = m%p; 
        if (nn < mm) return 0; 
        //fac[nn]為預處理的 fac[n] = n!%p   
        ret = ret*fac[nn]*PowerMod(fac[mm]*fac[nn-mm]%p, p-2, p)%p; 
        n /= p; 
        m /= p; 
    } 
    return ret; 
} 
//C(n, m) % p  
Lucas(n, m, p); 

ll Lucas(ll n, ll m, ll p) {
    ll ret = 1;
    while (n && m) {
        ll nn = n%p, mm = m%p;
        if (nn < mm) return 0;
        //fac[nn]為預處理的 fac[n] = n!%p
        ret = ret*fac[nn]*PowerMod(fac[mm]*fac[nn-mm]%p, p-2, p)%p;
        n /= p;
        m /= p;
    }
    return ret;
}
//C(n, m) % p
Lucas(n, m, p);

AC代碼：

[cpp] #include <cstdio>  
#include <algorithm>  
#include <cmath>  
#include <iostream>  
using namespace std; 
 
typedef long long ll; 
ll fac[100003]; 
 
void init(ll p) { 
    fac[0] = 1; 
    for (int i=1; i<=p; i++) fac[i] = fac[i-1]*i%p; 
} 
ll PowerMod(ll a, ll b, ll k) { 
    ll tmp = a, ret = 1; 
    while (b) { 
        if (b & 1) ret = ret * tmp % k; 
        tmp = tmp * tmp % k; 
        b >>= 1; 
    } 
    return ret; 
} 
ll Lucas(ll n, ll m, ll p) { 
    ll ret = 1; 
    while (n && m) { 
        ll nn = n%p, mm = m%p; 
        if (nn < mm) return 0; 
        ret = ret*fac[nn]*PowerMod(fac[mm]*fac[nn-mm]%p, p-2, p)%p; 
        n /= p; 
        m /= p; 
    } 
    return ret; 
} 
 
int main() { 
    int T; 
    ll n, m, p; 
    cin >> T; 
    while (T--) { 
        cin >> n >> m >> p; 
        init(p); 
        cout << Lucas(n+m, m, p) << endl; 
    } 
    return 0; 
} 

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

typedef long long ll;
ll fac[100003];

void init(ll p) {
    fac[0] = 1;
    for (int i=1; i<=p; i++) fac[i] = fac[i-1]*i%p;
}
ll PowerMod(ll a, ll b, ll k) {
    ll tmp = a, ret = 1;
    while (b) {
        if (b & 1) ret = ret * tmp % k;
        tmp = tmp * tmp % k;
        b >>= 1;
    }
    return ret;
}
ll Lucas(ll n, ll m, ll p) {
    ll ret = 1;
    while (n && m) {
        ll nn = n%p, mm = m%p;
        if (nn < mm) return 0;
        ret = ret*fac[nn]*PowerMod(fac[mm]*fac[nn-mm]%p, p-2, p)%p;
        n /= p;
        m /= p;
    }
    return ret;
}

int main() {
    int T;
    ll n, m, p;
    cin >> T;
    while (T--) {
        cin >> n >> m >> p;
        init(p);
        cout << Lucas(n+m, m, p) << endl;
    }
    return 0;
}