Unknown Treasure
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 721 Accepted Submission(s): 251
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\leq 20)$ representing the number of test cases.
Each test case starts with three integers $n,m,k(1\leq m\leq n\leq 10^{18},1\leq k\leq 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=p_1⋅p_2\cdots p_k\leq 10^{18}\, and\, p_i\leq 10^5 for\, every\, i\in\{1,\dots,k\}.$
Output
For each test case output the correct combination on a line.
Sample Input
1
9 5 2
3 5
Sample Output
6
Source
解题：中国剩余定理+Lucas定理
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = ;
LL F[maxn] = {},a[maxn],m[maxn],N,M,n;
void init(LL mod){
for(int i = ; i < maxn; ++i)
F[i] = F[i-]*i%mod;
}
LL quickPow(LL base,LL index,LL mod){
LL ret = ;
base %= mod;
while(index){
if(index&) ret = ret*base%mod;
index >>= ;
base = base*base%mod;
}
return ret;
}
LL Inv2(LL b,LL mod){
return quickPow(b,mod-,mod);
}
LL Lucas(LL n,LL m,LL mod){
LL ret = ;
while(n && m){
LL a = n%mod;
LL b = m%mod;
if(a < b) return ;
ret = ret*F[a]%mod*Inv2(F[b]*F[a-b]%mod,mod)%mod;
n /= mod;
m /= mod;
}
return ret;
}
LL mul(LL a,LL b,LL mod){
if(!a) return ;
return ((a&)*b%mod + (mul(a>>,b,mod)<<)%mod)%mod;
}
LL CRT(LL a[],LL m[],LL n){
LL M = ,ret = ;
for(int i = ; i < n; ++i) M *= m[i];
for(int i = ; i < n; ++i){
LL x,y,tm = M/m[i];
x = Inv2(tm,m[i]);
ret = (ret + mul(mul(tm,x,M),a[i],M))%M;
}
return ret;
}
int main(){
int kase;
scanf("%d",&kase);
while(kase--){
scanf("%I64d%I64d%I64d",&N,&M,&n);
for(int i = ; i < n; ++i){
scanf("%I64d",m + i);
init(m[i]);
a[i] = Lucas(N,M,m[i]);
}
printf("%I64d\n",CRT(a,m,n));
}
return ;
}