http://acm.hdu.edu.cn/showproblem.php?pid=5446
题意：题目意思很简单，要你求C(n,m)mod p的值 p=p1*p2*...pn;
题解：对于C(n,m)mod p 由于n,m的值很大 我们用lucas定理把n,m的范围缩小。由于模数是由若干个素数的乘积组成，那么对于最终要求的解x，我们可以用中国剩余定理求解。中国剩余定理如下：
设正整数两两互素，则同余方程组
有整数解。并且在模下的解是唯一的，解为
其中，而
为
模
的逆元。
最后说一点，由于数据的范围还是比较大，在乘法求解的过程中，如果用普通的乘法，是会溢出的，这里还要用到按位乘法（具体看代#include <cstdio>#include <iostream>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
ll m[],a[];
ll mul(ll a,ll b,ll p)// 按位乘
{
ll ret=;
while(b)
{
if(b&) ret=(ret+a)%p;
b=b>>;
a=(a+a)%p;
}
return ret; }
ll exgcd(ll a,ll b,ll &x,ll &y)// 扩展欧几里得
{
if(b==)
{
x=;
y=;
return a;
}
ll temp=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return temp;
}
ll finv(ll a,ll m)// 求逆元
{
ll x,y;
ll g=exgcd(a,m,x,y);
x=(x%m+m)%m;//
return x;
}
ll c(ll n,ll m,ll p)
{
if(m > n) return ;
ll a,b;
a=b=;
while(m)
{
a=(a*n)%p;
b=b*m%p;
n--;
m--;
}
return mul(a,finv(b,p),p);
}
ll lucas(ll n,ll m,int p)
{
if(m==) return ;// c(n,0)=1;
return mul(lucas(n/p,m/p,p),c(n%p,m%p,p),p);// lucas把组合数要求解的范围缩小到了p之内
} ll crt(int len)
{
ll sum=;
ll M=;
for(int i=;i<=len;i++) M*=m[i];
for(int i=;i<=len;i++)
{
ll temp=M/m[i];
sum=(sum+mul(mul(a[i],temp,M),finv(temp,m[i]),M))%M;// 这里有一个数据溢出的问题 对于相乘数据会溢出的问题 用转为二进制的按位乘法
}
return sum;
} void init(ll p)
{
fac[]=;
fac[]=;
for(ll i=;i<=p;i++) fac[i]=fac[i]*i%p;
}
int main()
{
cin.sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
ll n,mm,k;
cin>>n>>mm>>k;
init(k);
for(int i=;i<=k;i++)
{
cin>>m[i];
a[i]=lucas(n,mm,m[i]);
}
cout<<crt(k)<<endl;
}
return ;
}