Link

http://acm.hdu.edu.cn/showproblem.php?pid=5446

Problem

On the way to the next secret treasure hiding place, the mathematician discovered a cave unknown to the map. The mathematician entered the cave because it is there. Somewhere deep in the cave, she found a treasure chest with a combination lock and some numbers on it. After quite a research, the mathematician found out that the correct combination to the lock would be obtained by calculating how many ways are there to pick m different apples among n of them and modulo it with m. m is the product of several different primes.

Mean

求C(N, M)%P,其中NMP最大可到10^18。其中为N个素数相乘P=p1*p2*…*pn,pi<10^5.

Analysis

可以先求出C(N, M)%pi,数据范围刚好可以用Lucas定理求解。

这样就相当于N个模线性方程组,然后刚好可以用China定理求。

在China定理中相乘会超出longlong,因此使用快速乘法。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N, M, K;
ll pi[12], mi[12];

// 求C(n, m) % p, O(p*logp(n))
// 1 <= m <= n <= 10^18 和 2 <= p <= 10^5 (p 是素数)

ll quickpow(ll m, ll n, ll k) {
    ll res = 1, base = m;
    while(n > 0) {
        if(n & 1)
            res = (res * base) % k;
        base = (base * base) % k;
        n >>= 1;
    }
    return res % k;
}

ll quickMulti(ll x, ll y, ll p) {
    ll ret = 0;
    for(; y ; y >>= 1) {
        if(y & 1) ret = (ret + x) % p;
        x = (x + x) % p;
    }
    return ret;
}


ll Comb(ll n, ll m, ll p) {
    if (m > n) return 0;
    m = min(m, n - m);
    ll zi = 1, mu = 1;
    for (ll i = 0; i < m; i++) {
        zi = zi * (n - i) % p;
        mu = mu * (i + 1) % p;
    }
    return zi * quickpow(mu, p - 2, p) % p;
}
ll Lucas(ll n, ll m, ll p) {
    if (m == 0) return 1;
    return Comb(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}

// ax + by = gcd(a, b) = g;
void exgcd(ll a, ll b, ll &g, ll &x, ll &y) {
    if(!b) { g = a; x = 1; y = 0; }
    else { exgcd(b, a%b, g, y, x); y -= x*(a/b); }
}

// n个方程: x=a[i](mod m[i]) m必须两两互质
ll china(ll n, ll *a, ll *m) {
    ll M = 1, d, y, x = 0;
    for(int i = 0; i < n; ++i)
        M *= m[i];
    for (int i = 0; i < n; ++i) {
        ll w = M / m[i];
        exgcd(m[i], w, d, d, y);
        x = (x + quickMulti(quickMulti(y, w, M), a[i], M)) % M;
        //x = (x + y * w * a[i]) % M;
    }
    return (x + M) % M;
}



int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%I64d%I64d%I64d", &N, &M, &K);
        for(int i = 0; i < K; ++i) {
            scanf("%I64d", pi + i);
            mi[i] = Lucas(N, M, pi[i]);
        }
        ll ans = china(K, mi, pi);
        printf("%I64d\n", ans);
    }
    return 0;
}

欢迎留言