HDU5446 Unknown Treasure（组合数膜合数-->Lucas+中国剩余定理）

>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

Input

On the first line there is an integer $T (T \leq 20)$ OutputFor each test case output the correct combination on a line.Sample Input

1
9 5 2
3 5

Sample Output

题意：

让你求出C(n,m)%M的值。

思路：

此题的 n和m非常大，因此不能用快速幂取模，这里我们只能用lucas定理，但lucas定理有一个条件，要求C(n,m)%M的M必须要为素数，因此，我们又要用到中国剩余定理。

经验：

按照这样的方法，现在大的组合数都可以化小了。
注意long long范围，超范围时用快速乘法的方法做乘，欧拉算法时里有用过。即代码里的mul()函数。

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=100010;
LL fac[maxn],mod[maxn],odd[maxn],M,Mod;
void factorial()
{
    fac[0]=1;  for(int i=1;i<=Mod;i++) fac[i]=fac[i-1]*i%Mod;
}
LL f_pow(LL a,LL x)
{
    LL res=1; a%=Mod;
    while(x){  if(x&1) res=res*a%Mod;a=a*a%Mod; x>>=1; }return res;
}
LL C(LL n,LL m)
{
    if(m>n) return 0; return fac[n]*f_pow(fac[m]*fac[n-m]%Mod,Mod-2)%Mod;
}
LL Lucas(LL n,LL m)
{
    if(m==0) return 1;  return C(n%Mod,m%Mod)*Lucas(n/Mod,m/Mod)%Mod; 
}
LL mul(LL x,LL y,LL p)
{
    LL res=0;
    while(y){
        if(y&1) res=(res+x)%p;y>>=1;x=(x+x)%p;
    }return res%p;
}
void China(int k)
{
    LL ans=0;
    for(int i=1;i<=k;i++){
        Mod=mod[i];
        ans=ans+mul(mul(M/mod[i],f_pow(M/mod[i],mod[i]-2),M),odd[i],M);
    }printf("%lld
",(ans+M)%M);
}
int main()
{    
    LL T,n,m,k;
    scanf("%lld",&T);
    while(T--){
        M=1;
        scanf("%lld%lld%lld",&n,&m,&k);
        for(int i=1;i<=k;i++){
            scanf("%d",&mod[i]);Mod=mod[i];M*=mod[i];
            factorial();
            odd[i]=Lucas(n,m)%Mod;
        }
        China(k);
    }return 0;
}

再总结一下剩余定理

设正整数两两互素，则同余方程组

有整数解。并且在模下的解是唯一的，解为

其中，而为模的逆元。