Unknown Treasure
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2389 Accepted Submission(s): 885
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≤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}
.
Output
For each test case output the correct combination on a line.
Sample Input
1
9 5 2
3 5
9 5 2
3 5
Sample Output
6
Source
题意：C(n,m)%p1*p2*p3..pk
题解：中国剩余定理+lucas
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll __int64
#define mod 10000000007
using namespace std;
ll n,m,k;
int t;
ll exm;
ll f[];
void init(int p) { //f[n] = n!
f[] = ;
for (int i=; i<=p; ++i) f[i] = f[i-] * i % p;
}
ll mulmod(ll x,ll y,ll m)
{
ll ans=;
while(y)
{
if(y%)
{
ans+=x;
ans%=m;
}
x+=x;
x%=m;
y/=;
}
ans=(ans+m)%m;
return ans;
} void exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == )
{
x = ;
y = ;
return;
}
exgcd(b, a % b, x, y);
ll tmp = x;
x = y;
y = tmp - (a / b) * y;
} ll pow_mod(ll a, ll x, int p) {
ll ret = ;
while (x) {
if (x & ) ret = ret * a % p;
a = a * a % p;
x >>= ;
}
return ret;
}
ll CRT(ll a[],ll m[],ll n)
{
ll M = ;
ll ans = ;
for(ll i=; i<n; i++)
M *= m[i];
for(ll i=; i<n; i++)
{
ll x, y;
ll Mi = M / m[i];
exgcd(Mi, m[i], x, y);
ans = (ans +mulmod( mulmod( x , Mi ,M ), a[i] , M ) ) % M;
}
ans=(ans + M )% M;
return ans;
} ll Lucas(ll n, ll k, ll p) { //C (n, k) % p
init(p);
ll ret = ;
while (n && k) {
ll nn = n % p, kk = k % p;
if (nn < kk) return ; //inv (f[kk]) = f[kk] ^ (p - 2) % p
ret = ret * f[nn] * pow_mod (f[kk] * f[nn-kk] % p, p - , p) % p;
n /= p, k /= p;
}
return ret;
}
int main ()
{
scanf("%d",&t);
{
for(int i=;i<=t;i++)
{
ll ee[];
ll gg[];
scanf("%I64d %I64d %I64d",&n,&m,&k);
for(ll j=;j<k;j++)
{
scanf("%I64d",&exm);
gg[j]=exm;;
ee[j]=Lucas(n,m,exm);
}
printf("%I64d\n",CRT(ee,gg,k));
}
}
return ;
}