hdu 5446（中国剩余+lucas+按位乘）

题意：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
",china(k,an,p));
    }
    return 0;
}