题目链接:Unknown Treasure

这道题求得实际上是C(n,m)%M,M=p1·p2·p3···pk。又因为pi都是素数，故可用卢卡斯定理。但这里不可以直接用Lucas，因为Lucas的使用条件是“C(n,m)很大，但p不太大，同时p为素数”，而这里的M可能会很大。故我们可以先求C(n,m)%p1,C(n,m)%p2,C(n,m)%pk，然后再利用中国剩余定理得到最终答案。

代码如下:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long LL;
//从n个苹果中挑出m个相互不同的苹果
LL mulq(LL a,LL b,LL m)        //(a*b)%m
{    
    LL ans=0;
    while(b)
    {
        if(b&1)
            ans=(ans+a)%m;
        a=(a+a)%m;
        b>>=1;
    }
    return ans;
}
LL powq(LL a,LL b,LL mod)
{
    LL ans=1;a%=mod;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1; 
    }
    return ans;
} 
LL inv(LL x,LL p)
{
    return powq(x,p-2,p);
}
LL comb(LL n,LL m,LL p)
{
    if(n<m||m<0)
        return 0;
    LL up=1;
    LL down=1;
    for(LL i=n-m+1;i<=n;i++)
        up=(up*i)%p;
    for(LL i=1;i<=m;i++)
        down=(down*i)%p;
    return up*inv(down,p)%p;
}
LL lucas(LL a,LL b,LL p)
{
    return !b?1:lucas(a/p,b/p,p)*comb(a%p,b%p,p)%p;
}
LL china(int k,LL a[],LL m[])
{
    LL M=1;LL ans=0;
    for(int i=0;i<k;i++)
        M*=m[i];
    for(int i=0;i<k;i++)
    {
        LL tmp=M/m[i];        //tmp==>mi        
        ans=(ans+mulq(tmp*inv(tmp,m[i]),a[i],M))%M;        //ti==>ti*mi=1 (mod mi)
    }
    return (ans+M)%M;            //通解为kM+∑(i=0,k)(ai*ti*Mi) 
}
int main()
{
    LL t,k;
    LL n,m;
    int cnt;
    LL r[15],md[15];
    scanf("%d",&t);
    while(t--)
    {    
        cnt=0;
        memset(r,0,sizeof(r));
        memset(md,0,sizeof(md));
        scanf("%lld %lld %lld",&n,&m,&k);
        for(int i=0;i<k;i++)
        {
            LL tmp=1;
            scanf("%lld",&tmp);
            md[cnt]=tmp;
            r[cnt++]=lucas(n,m,tmp);
        }
        LL pro=1;
        for(int i=0;i<k;i++)    
            pro*=md[i];
        LL ans=china(k,r,md);        //为什么答案就是中国剩余定理求出的值？不应该再模上乘积吗? 
        printf("%lld\n",ans%pro);    //因为中国剩余定理在计算时已经算了这个模;中国剩余定理求出的是解集中的最小解，即c(m,m)%M;
                                    //当然，如果在main中再模一次M,也是可以AC的    
    }
    return 0;
}