Unknown Treasure
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 1662 Accepted Submission(s): 617
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.
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}.
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≤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
Sample Output
6
Source
Recommend
题目大意：给n,m,k,就是求c(n,m)对下边k个素数取余
ac代码
#include<stdio.h>
#include<string.h>
#define LL __int64
LL fac[12][100005],M[12];
LL tp[12];
void get_fact(LL k)
{
int i,j;
for(i=0;i<k;i++)
{
fac[i][0]=1;
for(j=1;j<=tp[i];j++)
fac[i][j]=(fac[i][j-1]*j)%tp[i];
}
}
LL qpow(LL a,LL b,LL mod)
{
LL ans=1;
while(b)
{
if(b&1)
ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return ans%mod;
}
LL lucas(LL n,LL m,int x)
{
LL ans=1;
if(n<m)
return 0;
while(n&&m)
{
LL a=n%tp[x];
LL b=m%tp[x];
if(a<b)
return 0;
ans=(ans*fac[x][a]*qpow(fac[x][b]*fac[x][a-b]%tp[x],tp[x]-2,tp[x]))%tp[x];
n/=tp[x];
m/=tp[x];
}
return ans;
}
void exgcd(LL a,LL b,LL &x,LL &y)
{
if(b==0)
{
x=1;
y=0;
return;
}
exgcd(b,a%b,x,y);
LL t=x;
x=y;
y=t-a/b*y;
}
LL CRT(int k)
{
LL a1,b1,a2,b2,a,b,c,x,y;
a1=tp[0],b1=M[0];
for(int i=1;i<k;i++)
{
a2=tp[i],b2=M[i];
a=a1;b=a2;c=b2-b1;
exgcd(a,b,x,y);
x=((c*x)%b+b)%b;
b1=b1+a1*x;
a1=a1*b;
}
return b1;
}
int main()
{
LL n,g;
int t;
scanf("%d",&t);
while(t--)
{
LL n,m,k;
scanf("%I64d%I64d%I64d",&n,&m,&k);
LL i;
int j;
memset(M,0,sizeof(M));
for(i=0;i<k;i++)
{
scanf("%I64d",&tp[i]);
// M[j]=(M[j]+lucas(n,m,i))%tp[i];
}
get_fact(k);
for(i=0;i<k;i++)
{
M[i]=(M[i]+lucas(n,m,i))%tp[i];
}
printf("%I64d\n",CRT(k));
}
}