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

Input

On the first line there is an integer

Output

For each test case output the correct combination on a line.

Sample Input

1 9 5 2 3 5

Sample Output

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

Unknown Treasure

推荐阅读