hdu-5446(中国剩余定理+lucas）

心已赠人 2022-06-10 11:48 287阅读 0赞

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  *p*1,...,*p**k*. It is guaranteed that  *M*=*p*1⋅*p*2⋅⋅⋅*p**k*≤1018 and  *p**i*≤105 for every  *i*∈\{ 1,...,*k*\}.

Output

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

Sample Input

1 9 5 2 3 5

Sample Output

题目题意:题目意思很简单，就是让我们求组合数C(n,m)%M的数值。

题目分析:我们知道，对于组合数C(n,m)%mod，很容易想到的就是lucas，但是lucas有一个限定，就是后面的mod必须是素数，而这个题目中的M肯定不会是素数，因为它是几个素数的乘积，那么应该怎么办了，其实M的这种形式（几个素数的乘积形式），给了我们一点提示，就是不能直接用M去模。应该分开去模，而且单个的pi也是素数，正好满足Lucas的条件。

b\[1\]=C(n,m)%p\[1\];

.....

b\[i\]=C(n,m)%p\[i\];

解出了所有的b\[i\],现在我们就反解回去，得到X=b\[1\]%p\[i\]，，，，X=b\[i\]%p\[i\]几组同于方程，求解这几组同于方程，很明显得用中国剩余定理了。

代码写得不好，里面用了很多的函数，注释会表明每个函数的用途的！

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #define ll long long
    using namespace std;
    
    const int maxn=1e5+10;
    ll p[15],b[15],n,m;
    ll fac[maxn],inv[maxn];
    
    ll fast_pow(ll base,ll k,ll mod)//快速幂运算
    {
        ll ans=1;
        while (k) {
            if (k&1)
                ans=ans*base%mod;
            base=base*base%mod;
            k>>=1;
        }
        return ans;
    }
    
    ll fast_mul(ll a,ll b,ll mod)//快速乘法a*b%mod，因为在代码里面运算时，乘法会炸long long
    {
        ll ans = 0;
       while(b){
          if(b&1)
             ans = (ans+a)%mod;
           a = (a+a)%mod;
           b >>= 1;
        }
        return ans;
    }
    
    void init(ll n,ll m,ll mod)//预处理，求n!,和m!(n-m)!的逆元,逆元是费马小定理
    {
        fac[0]=fac[1]=1;
        for (ll i=2;i<=n;i++)
            fac[i]=fac[i-1]*i%mod;
        inv[m]=fast_pow(fac[m],mod-2,mod);
        inv[n-m]=fast_pow(fac[n-m],mod-2,mod);
    }
    
    ll com(ll n,ll m,ll mod)//求C(n,m)%mod
    {
        if (m>n) return 0;
        if (m==n) return 1;
        init(n,m,mod);
        return fac[n]*inv[n-m]%mod*inv[m]%mod;
    }
    
    ll lucas(ll n,ll m,ll mod)//lucas
    {
        if (m==0)
            return 1;
        return fast_mul(lucas(n/mod,m/mod,mod),com(n%mod,m%mod,mod),mod);//乘法会爆ll,
    
    }
    
    ll exgcd(ll a,ll b,ll &x,ll &y)
    {
       if (b==0) {
          x=1;
          y=0;
          return a;
       }
       ll r=exgcd(b,a%b,x,y);
       ll t=x;
       x=y;
       y=t-a/b*y;
       return r;
    }
    
    void CRT(ll a[],ll m[],int n)
    {
        ll w=1;
        ll ans=0;
        for (int i=0;i<n;i++)
            w=w*m[i];
        for (int i=0;i<n;i++) {
            ll x,y;
            ll mi=w/m[i];
            exgcd(mi,m[i],x,y);
        ans=(ans+fast_mul(fast_mul(x,mi,w),a[i],w))%w;//这里的乘法会爆ll
        }
        if (ans<0) ans+=w;
        printf("%lld\n",ans);
    }
    
    int main()
    {
        int t,k;
        scanf("%d",&t);
        while (t--) {
            scanf("%lld%lld%d",&n,&m,&k);
            for (int i=0;i<k;i++)
               scanf("%lld",&p[i]);
            for (int i=0;i<k;i++)
                b[i]=lucas(n,m,p[i]);//求出每一组bi
            CRT(b,p,k);
        }
        return 0;
    }