题目链接：

Unknown Treasure

问题描述

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.

输入

On the first line there is an integer T(T≤20) representing the number of test cases.

Each test case starts with three integers n,m,k(1≤m≤n≤1018,1≤k≤10) on a line where k is the number of primes. Following on the next line are k different primes p1,...,pk. It is guaranteed that M=p1⋅p2⋅⋅⋅pk≤1018 and pi≤105 for every i∈{1,...,k}.

输出

For each test case output the correct combination on a line.

样例

sample input

1

9 5 2

3 5

sample output

6

题意

求C[n][m]%(P1 * P2 * P3 * ... * pk)

题解

由于n,m都特别大，所以我们用卢卡斯定理对C[n][m]进行pi进制的拆项得到结果ai，用卢卡斯定理的时候p不能太大，否则就没有意义了，所以我们不能直接用M=P1 * P2 * P3 * ... * pk（而且这个不是质数！！！）进行拆项。

然后对所有的ai用中国剩余定理求出C[n][m]%(P1 * P2 * P3 * ... * pk)。

代码

#include
    
     #include
     
      #include
      
       using namespace std;typedef long long LL;LL pi[22], a[22];LL mul(LL a, LL n, LL mod) {    LL ret = 0;    LL t1 = a, t2 = n;    while (n) {        //puts("mul");        if (n & 1) ret = (ret + a) % mod;        a = (a + a) % mod;        n >>= 1;    }    return ret;}void gcd(LL a, LL b, LL& d, LL& x, LL& y) {    if (!b) { d = a; x = 1; y = 0; }    else { gcd(b, a%b, d, y, x); y -= x*(a / b); }}LL inv(LL a, LL mod) {    LL d, x, y;    gcd(a, mod, d, x, y);    return d == 1 ? (x + mod) % mod : -1;}LL get_C(LL n, LL m, LL mod) {    if (n < m) return 0;    LL ret = 1;    for (int i = 0; i < m; i++) ret = ret*(n - i) % mod;    LL fac_m = 1;    for (int i = 1; i <= m; i++) fac_m = fac_m*i%mod;    return ret*inv(fac_m, mod) % mod;}LL lucas(LL n, LL m, LL mod) {    if (m == 0) return 1LL;    return get_C(n%mod, m%mod, mod)*lucas(n / mod, m / mod, mod) % mod;}LL china(int n) {    LL M = 1, d, y, x = 0;    for (int i = 0; i < n; i++) M *= pi[i];    for (int i = 0; i < n; i++) {        LL w = M / pi[i];        gcd(pi[i], w, d, d, y);        x = (x + mul(mul(y, w, M), a[i], M)) % M;    }    return (x + M) % M;}int main() {    int tc;    scanf("%d", &tc);    while (tc--) {        LL n, m; int k;        scanf("%lld%lld%d", &n, &m, &k);        for (int i = 0; i < k; i++) {            scanf("%lld", &pi[i]);            a[i] = lucas(n, m, pi[i]);        }        LL ans = china(k);        printf("%lld\n", ans);    }    return 0;}