hdu_5446 Unknown Treasure

题目:

  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.

思路:

  根据Lucas定理可得:
  靠这个就能求出的值了。
  因为都是质数,所以直接列出同余方程就能得到的值了。
  ps:Lucas定理求组合数的时候要特判不符合的情况。

代码:

#include <bits/stdc++.h>
#define MAXN 100005
#define ll long long
using namespace std;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
#define lcm(a,b) ((a)/gcd(a,b)*(b))
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){d=a;x=1;y=0;return;}
    exgcd(b,a%b,d,y,x);y-=a/b*x;
}
ll mul(ll a,ll b,ll m){
    a=(a%m+m)%m;
    b=(b%m+m)%m;
    if(a>b)swap(a,b);
    ll ans=0;
    while(a){
        if(a&1)(ans+=b)%=m;
        (b<<=1)%=m;
        a>>=1;
    }
    return ans;
}
ll calc(ll a,ll b,ll c){
    ll d,x,y;
    exgcd(a,b,d,x,y);
    if(c%d)return -1;
    b/=d;c/=d;
    return (mul(x,c,b)+b)%b;
}
struct CRT{
    ll A,M;
    CRT(){A=0;M=1;}
    bool insert(ll a,ll m){
        ll k=calc(M,m,a-A);
        if(!~k)return false;
        A+=M*k;
        M=lcm(M,m);
        return true;
    }
};
ll inv(ll a,ll m){
    ll x,y,d;
    exgcd(a,m,d,x,y);
    return (x%m+m)%m;
}
ll fac[MAXN]={1},invfac[MAXN]={1};
ll C(ll n,ll m,ll mod){    
    if(m<n)return 0;
    return fac[m]*invfac[n]%mod*invfac[m-n]%mod;
}
ll lucas(ll a,ll b,ll m){
    if(!a)return 1;
    return lucas(a/m,b/m,m)*C(a%m,b%m,m)%m;
}
void init(ll p){
    for(int i=1;i<p;i++)
        fac[i]=(fac[i-1]*i)%p;
    invfac[p-1]=inv(fac[p-1],p);
    for(int i=p-2;~i;i--)
        invfac[i]=invfac[i+1]*(i+1)%p;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        CRT crt;
        ll n,m,p;
        int k;
        scanf("%lld%lld%d",&n,&m,&k);
        for(int i=1;i<=k;i++){
            scanf("%lld",&p);
            init(p);
            crt.insert(lucas(m,n,p),p);
        }
        printf("%lld\n",crt.A);
    }
    return 0;
}