题意：c( n, m)%M M = P1 * P2 * ......* Pk
Lucas定理是用来求 c(n,m) mod p，p为素数的值。得出一个存余数数组，在结合中国剩余定理求值
其中有个地方乘积可能超范围，所以按位乘（数论方面薄弱啊，学习学习）。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll; ll p[15],an[15];
ll fac[100005],inv[100005]; ll pow_mod(ll a, int n, int mod)
{
ll ret = 1;
while (n)
{
if (n&1) ret = ret * a % mod;
a = a * a % mod;
n >>= 1;
}
return ret;
} void ini(int x)
{
fac[0] = 1;
for(int i = 1; i < x; i++) fac[i] = fac[i-1]*i%x;
inv[x - 1] = pow_mod(fac[x-1],x-2,x);
for(int i = x - 2; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % x;
} ll c(ll a,ll b,ll p)
{
if(a < b || a < 0 || b < 0)
return 0;
return fac[a]*inv[b]%p*inv[a-b]%p;
} ll lucas(ll a,ll b, int p)
{
if( b == 0)
return 1;
return lucas(a/p,b/p,p)*c(a%p,b%p,p)%p;
} ll ex_gcd(ll a, ll b, ll& x, ll& y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = ex_gcd(b, a % b, y, x);
y -= x * (a / b);
return d;
} ll mul(ll a, ll b, ll mod)
{
a = (a % mod + mod) % mod;
b = (b % mod + mod) % mod; ll ret = 0;
while(b)
{
if(b&1)
{
ret += a;
if(ret >= mod) ret -= mod;
}
b >>= 1;
a <<= 1;
if(a >= mod) a -= mod;
}
return ret;
} ll china(ll n,ll* a,ll* b)
{
ll M = 1,d,y,x= 0;
for(int i = 0; i < n; i++)
{
M *= b[i];
}
for(int i = 0; i < n; i++)
{
ll w = M/b[i];
ex_gcd(b[i],w,d,y);
x = (x + mul(mul(y, w, M), a[i], M));//可能超范围
}
return (x+M) % M;
} int main()
{
int T,k;
ll n,m;
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d",&n,&m);
scanf("%d",&k);
for(int i = 0; i < k; i++)
{
scanf("%I64d",&p[i]);
ini(p[i]);
an[i] = lucas(n,m,p[i]);
}
printf("%I64d\n",china(k,an,p));
}
return 0;
}