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<stdio.h>

  2 #include<algorithm>

  3 #include<iostream>

  4 #include<string.h>

  5 #include<stdlib.h>

  6 #include<queue>

  7 #include<map>

  8 #include<math.h>

  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<nn)

 39                         return 0;

 40                 else

 41                 {

 42                         LL ni=a[mm-nn]*a[nn]%p;

 43                         ni=a[mm]*quick(ni,p-2,p)%p;

 44                         return ni*lucas(n/p,m/p,p);

 45                 }

 46         }

 47 }

 48 LL mul(LL n, LL m,LL p)

 49 {

 50         n%=p;

 51         m%=p;

 52         LL ret=0;

 53         while(m)

 54         {

 55                 if(m&1)

 56                 {

 57                         ret=ret+n;

 58                         ret%=p;

 59                 }

 60                 m>>=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 }

巴特西

Unknown Treasure(hdu5446)

Unknown Treasure

最新文章

热门文章