Unknown Treasure

**Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2112 Accepted Submission(s): 771
**

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

9 5 2

3 5

Sample Output

题意：就是让你求组合数C(n,m)的值模M=p1*p2*…pk的值这写p；

思路：中国剩余定理+lucas定理；

因为组合数比较大，模数乘起来也很大，所以我们先用lucas定理求出对每个模数所求得的模，然后再通过中国剩余定理求对那个大模数的模；

在使用中国剩余定理的时候，最后那个M可能会很大，所以乘法的时候可能会爆LL，要用快速乘去处理

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 using namespace std;
10 typedef long long LL;
11 int mod[20];
12 LL a[100005];
13 LL yu[30];
14 LL quick(LL n,LL m,LL p)
15 {
16 LL ans=1;
17 while(m)
18 {
19 if(m&1)
20 {
21 ans=ans*n%p;
22 }
23 n=n*n%p;
24 m/=2;
25 }
26 return ans;
27 }
28 LL lucas(LL n,LL m,LL p)
29 {
30 if(n==0)
31 {
32 return 1;
33 }
34 else
35 {
36 LL nn=n%p;
37 LL mm=m%p;
38 if(mm>=1;
61 n<<=1;
62 n%=p;
63 }
64 return ret;
65 }
66 int main(void)
67 {
68 LL n,m;
69 int k;
70 int t;
71 scanf("%d",&k);
72 int i,j;
73 while(k--)
74 {
75 scanf("%lld %lld %d",&n,&m,&t);
76 for(i=0; i<t; i++)
77 {
78 scanf("%d",&mod[i]);
79 a[0]=1;
80 a[1]=1;
81 for(j=2; j<mod[i]; j++)
82 {
83 a[j]=a[j-1]*j%mod[i];
84 }
85 yu[i]=lucas(m,n,mod[i]);
86 }
87 LL sum=1;
88 for(i=0; i<t; i++)
89 {
90 sum*=(LL)mod[i];
91 }
92 LL acc=0;
93 for(i=0; i<t; i++)
94 {
95 LL kk=sum/mod[i];
96 LL ni=quick(kk%mod[i],mod[i]-2,mod[i]);
97 acc=(acc+mul(yu[i],mul(kk,ni,sum),sum)%sum)%sum;
98
99 }
100 acc=acc%sum+sum;
101 acc%=sum;
102 printf("%lld\n",acc);
103 }
104 return 0;
105 }

手机扫一扫

移动阅读更方便

你可能感兴趣的文章