(HDU) 5446 Unknown Treasure [Lucas + 中國剩餘]

http://acm.hdu.edu.cn/showproblem.php?pid=5446

這題是求 C(n,m) % P，其中，P = p1*p2*p3*......*pk，p1, p2, p3, ...... , pk <= 10**5

對於一個p，我們可以用 Lucas 定理求出C(n,m) % p，可以得到k組類似的東西

Lucas 定理用法：求出 C(n,m)%p 時，把n, m 且成p進制下的整數

n = (n0, n1, n2, n3, n4, ......) , n = n0 + n1 * p + n2 * p^2 + ......
m = (m0, m1, m2, m3, m4 ......), m = m0 + m1 * p + m2 * p^2 + ......

這時，答案就是C(n0,m0) * C(n1,m1) * C(n2,m2) * ......... ，特別的是，若C(x,y)中，x < y，則我們定義C(x,y) = 0

至於怎麼把那k組湊起來呢？就可以利用中國剩餘定理！(而且這題的mod都是質數，可以套公式解XDD)

中國剩餘的公式解：

x === a1 % m1
x === a2 % m2
......

其中，令 M = m1 * m2 * ......... ，m_i = M / m_i, t_i = m_i^(-1) (mod m1)
則答案為 a1*t1*m1 + a2*t2*m2 + .......

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cassert>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long      LL;
typedef long double    ld;
typedef pair<int,int>  pii;
typedef pair<LL,LL>    pLL;
typedef vector<int>    vint;
typedef vector<LL>     vLL;
typedef vector<pii>    vpii;
typedef vector<pLL>    vpLL;

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL);
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL,(f)*1LL);

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

#define IOS ios::sync_with_stdio(0); cin.tie(0);

int myRnd() {
    return abs(  ((rand()<<15) ^ rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)^rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 2e5 + 6;

int a[N];

LL ppow(LL a,LL n,LL mod)
{
    if (n==0) return 1%mod;
    else if (n==1) return a%mod;
    a%=mod;
    LL ret = ppow(a,n/2,mod);
    ret *= ret;
    ret %= mod;
    if (n&1) ret *= a;
    return ret%mod;
}

LL f[N];

LL get_rev(LL x,LL mod)
{
    return ppow(x,mod-2,mod);
}

LL C(LL n,LL m,LL p)
{
    if (m > n) return 0;
    return f[n]*get_rev(f[m],p)%p*get_rev(f[n-m],p)%p;
}

LL solve(LL n,LL m,LL p)
{
    //return C(n,m) % p
    vint vn,vm;
    while (n)
    {
        vn.PB(n%p);
        n/=p;
    }
    while (m)
    {
        vm.PB(m%p);
        m/=p;
    }
    vn.resize(max(SZ(vn),SZ(vm)));
    vm.resize(max(SZ(vn),SZ(vm)));
    f[0] = f[1] = 1;
    for (int i=2;p>i;i++)
    {
        f[i] = f[i-1]*i;
        f[i] %= p;
    }
    LL ret = 1;
    for (int i=0;SZ(vn)>i;i++)
    {
        ret *= C(vn[i],vm[i],p);
        ret %= p;
    }
    return ret;
}

LL mm[N];
LL t[N];

LL mul(LL a,LL b,LL mod)
{
    //return a*b % mod
    a%=mod;
    b%=mod;
    LL ret=0;
    LL now = a;
    while (b)
    {
        if (b&1) ret += now;
        now += now;
        now%=mod;
        ret%=mod;
        b>>=1;
    }
    return ret;
}

LL solve2(vpLL Chinese)
{
    //X % c.F == c.S
    LL M=1;
    int n=SZ(Chinese);
    REP0(i,n)
    {
        M *= Chinese[i].S;
    }
    REP0(i,n)
    {
        mm[i] = M/Chinese[i].S;
        t[i] = ppow(mm[i],Chinese[i].S-2,Chinese[i].S);
    }
    LL ans=0;
    REP0(i,n)
    {
        //ans += Chinese[i].F*t[i]%M*mm[i]%M;
        ans += mul(Chinese[i].F,mul(t[i],mm[i],M),M);
        ans %= M;
    }
    return ans;
}

int main () {
    //srand(time(NULL));
    int T;
    Si(T);
    while (T--)
    {
        LL n,m,k;
        SLLL(n,m,k);
        vLL p;
        REP1(i,k)
        {
            LL x;
            SL(x);
            p.PB(x);
        }
        vpLL Chinese;
        REP0(i,k)
        {
            Chinese.PB(MP(solve(n,m,p[i]),p[i]));
        }
        PL(solve2(Chinese));
    }
}