首页 > 代码库 > HDU 5446 中国剩余定理+lucas

HDU 5446 中国剩余定理+lucas

2024-08-24 09:21:56   218人阅读

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
19 5 23 5
 

 

Sample Output
6
 

 

Source
2015 ACM/ICPC Asia Regional Changchun Online
 
题意：C(n,m)%p1*p2*p3..pk
题解：中国剩余定理+lucas
  1 #include<iostream>  2 #include<cstring>  3 #include<cstdio>  4 #include<algorithm>  5 #define ll __int64  6 #define mod 10000000007  7 using namespace std;  8 ll n,m,k;  9 int t; 10 ll exm; 11 ll f[1000010]; 12 void init(int p) {                 //f[n] = n! 13     f[0] = 1; 14     for (int i=1; i<=p; ++i) f[i] = f[i-1] * i % p; 15 } 16 ll mulmod(ll x,ll y,ll m) 17 { 18     ll ans=0; 19     while(y) 20     { 21         if(y%2) 22         { 23             ans+=x; 24             ans%=m; 25         } 26         x+=x; 27         x%=m; 28         y/=2; 29     } 30     ans=(ans+m)%m; 31     return ans; 32 } 33  34 void exgcd(ll a, ll b, ll &x, ll &y) 35 { 36     if(b == 0) 37     { 38         x = 1; 39         y = 0; 40         return; 41     } 42     exgcd(b, a % b, x, y); 43     ll tmp = x; 44     x = y; 45     y = tmp - (a / b) * y; 46 } 47  48 ll pow_mod(ll a, ll x, int p)   { 49     ll ret = 1; 50     while (x)   { 51         if (x & 1)  ret = ret * a % p; 52         a = a * a % p; 53         x >>= 1; 54     } 55     return ret; 56 } 57 ll CRT(ll a[],ll m[],ll n) 58 { 59     ll M = 1; 60     ll ans = 0; 61     for(ll i=0; i<n; i++) 62         M *= m[i]; 63     for(ll i=0; i<n; i++) 64     { 65         ll x, y; 66         ll Mi = M / m[i]; 67         exgcd(Mi, m[i], x, y); 68         ans = (ans +mulmod( mulmod( x , Mi ,M ), a[i] , M ) ) % M; 69     } 70     ans=(ans + M )% M; 71     return ans; 72 } 73  74 ll Lucas(ll n, ll k, ll p) {       //C (n, k) % p 75      init(p); 76      ll ret = 1; 77      while (n && k) { 78         ll nn = n % p, kk = k % p; 79         if (nn < kk) return 0;                   //inv (f[kk]) = f[kk] ^ (p - 2) % p 80         ret = ret * f[nn] * pow_mod (f[kk] * f[nn-kk] % p, p - 2, p) % p; 81         n /= p, k /= p; 82      } 83      return ret; 84 } 85 int main () 86 { 87     scanf("%d",&t); 88     { 89         for(int i=1;i<=t;i++) 90         { 91             ll ee[15]; 92             ll gg[15]; 93             scanf("%I64d %I64d %I64d",&n,&m,&k); 94             for(ll j=0;j<k;j++) 95             { 96                 scanf("%I64d",&exm); 97                 gg[j]=exm;; 98                 ee[j]=Lucas(n,m,exm); 99             }100             printf("%I64d\n",CRT(ee,gg,k));101         }102     }103     return 0;104 }

 

 

HDU 5446 中国剩余定理+lucas


联系
我们