#### HDU 5446 – Unknown Treasure [Lucas定理+中国剩余定理+快速乘法]

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.

### 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;
}
```