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
Sample Output
6
lucas定理+中国剩余定理
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100005;
LL T,n,m,k,a[maxn],b[maxn],f[maxn];
LL PowMod(LL a,LL b,LL MOD){
LL ret=1;
a=a%MOD;
while(b){
if(b&1) ret=(ret*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return ret;
}
LL C(LL n,LL m,LL p)
{
if (n<m) return 0;
if (n==m) return 1;
LL ans=1;
ans=f[n]*PowMod(f[n-m]*f[m],p-2,p)%p;
return ans;
}
LL lucas(LL n,LL m,LL p){
LL ret=1;
while(n&&m&&ret){
ret=ret*C(n%p,m%p,p)%p;
n/=p;
m/=p;
}
return ret;
}
void egcd(LL a,LL b,LL&d,LL&x,LL&y)
{
if (!b){d=a,x=1,y=0;}
else
{
egcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
LL lmes() {
LL M=a[0],R=b[0],x,y,d;
for (int i=1; i<k; i++) {
egcd(M,a[i],d,x,y);
if ((b[i]-R)%d) return -1;
x=(b[i]-R)/d*x%(a[i]/d);
R+=x*M;
M=M/d*a[i];
R%=M;
}
return (R+M)%M;
}
int main()
{
cin>>T;
while (T--)
{
cin>>n>>m>>k;
for (int i=0;i<k;i++)
{
cin>>a[i];
for (LL j=f[0]=1;j<=a[i];j++) f[j]=(f[j-1]*j)%a[i];
b[i]=(a[i]+lucas(n,m,a[i]))%a[i];
}
cout<<lmes()<<endl;
}
return 0;
}
标签:HDU,cave,Unknown,LL,Treasure,ret,maxn,line,MOD From: https://blog.51cto.com/u_15870896/5838875