Problem Description
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.
Input
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≤10^18,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≤10^18 and pi≤10^5 for every i∈{1,...,k}.
Output
For each test case output the correct combination on a line.
Sample Input
1
9 5 2
3 5
Sample Output
6
题目要求一个大组合数模几个素数乘积的结果。
大组合那块能通过Lucas得到对每个素数模的结果。
然后再通过互质型的中国剩余定理可以得到最终结果。
不过我的模板中国剩余定理里面乘法部分会爆long long。
然后用大数优化了乘法部分，通过大数乘大数，模完后返回小数。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <vector>
#define LL long long
#define UNIT 10 using namespace std; const int maxK = ;
LL n, m, s[maxK], prime[maxK];
int k; struct Bignum
{
int val[];
int len; Bignum()
{
memset(val, , sizeof(val));
len = ;
} Bignum operator=(const LL &a)
{
LL t, p = a;
len = ;
while (p >= UNIT)
{
t = p - (p/UNIT)*UNIT;
p = p / UNIT;
val[len++] = t;
}
val[len++] = p;
return *this;
} Bignum operator*(const Bignum &a) const
{
Bignum x;
int i, j, up;
int x1, x2;
for (i = ; i < len; i++)
{
up = ;
for (j = ; j < a.len; j++)
{
x1 = val[i]*a.val[j] + x.val[i+j] + up;
if (x1 >= UNIT)
{
x2 = x1 - x1/UNIT*UNIT;
up = x1 / UNIT;
x.val[i+j] = x2;
}
else
{
up = ;
x.val[i+j] = x1;
}
}
if (up != )
x.val[i+j] = up;
}
x.len = i + j;
while (x.val[x.len-] == && x.len > )
x.len--;
return x;
} LL operator%(const LL &a) const
{
LL x = ;
for (int i = len-; i >= ; --i)
x = ((x*UNIT)%a+val[i]) % a;
return x;
}
}; LL mulMod(LL x, LL y, LL p)
{
LL ans = ;
Bignum xx, yy;
xx = x;
yy = y;
xx = xx*yy;
ans = xx%p;
return ans;
} LL quickMod(LL a, LL b, LL p)
{
LL ans = ;
a %= p;
while (b)
{
if (b&)
{
ans = ans*a%p;
b--;
}
b >>= ;
a = a*a%p;
}
return ans;
} LL C(LL n, LL m, LL p)
{
if (m > n)
return ;
LL ans = ;
for(int i = ; i <= m; i++)
{
LL a = (n+i-m)%p;
LL b = i%p;
ans = ans*(a*quickMod(b, p-, p)%p)%p;
}
return ans;
} LL Lucas(LL x, LL y, LL p)
{
if (y == )
return ;
return C(x%p, y%p, p)*Lucas(x/p, y/p, p)%p;
} //EXGCD
//求解方程ax+by=d,即ax=d mod(b)
//扩展可求逆元
//O(logn)
void exgcd(LL a, LL b, LL &x, LL &y, LL &d)
{
if (b == )
{
x = ;
y = ;
d = a;
}
else
{
exgcd(b, a%b, y, x, d);
y -= a/b*x;
}
} //中国剩余定理（互质）
//其中a为除数数组,n为模数数组
LL CRT(LL *a, LL *n, int len)
{
LL N = , ans = ;
for (int i = ; i < len; i++)
{
N *= n[i];
}
for (int i = ; i < len; i++)
{
LL m = N / n[i];
LL x, y, d;
exgcd(m, n[i], x, y, d);
x = (x%n[i] + n[i]) % n[i];
//ans = (ans + m*a[i]*x%N) % N;
ans = (ans + mulMod(mulMod(m, a[i], N), x, N)) % N;
}
return ans;
} void input()
{
scanf("%I64d%I64d%d", &n, &m, &k);
for (int i = ; i < k; ++i)
scanf("%I64d", &prime[i]);
} void work()
{
for (int i = ; i < k; ++i)
s[i] = Lucas(n, m, prime[i]);
LL ans = CRT(s, prime, k);
printf("%I64d\n", ans);
} int main()
{
//freopen("test.in", "r", stdin);
int T;
scanf("%d", &T);
for (int times = ; times < T; ++times)
{
input();
work();
}
return ;
}