Lucas定理模板【bzoj2982】【combination】

（上不了p站我要死了，侵权度娘背锅）

就是一道裸的组合数题，挂上自己的Lucas模板。

Lucas其实相当于将n、m按p进制分解求组合数，再乘起来。

当n < m时组合数的值为零，于是我们发现一个数按p进制分解后的C(a,b)中a有一半的几率小于b，而一旦出现这种情况答案就是0。所以在用Lucas定理时会有很大的概率答案为0。

当然这并不是Lucas定理有问题。仔细想想，如果我们把C(n,m)化为阶乘的形式，由于n和m都大于p（模数），所以阶乘的项里面很可能包含p或p的倍数。一旦出现p的倍数，答案就是0了。

模板

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#ifdef WIN32

#define RIN "%I64d"

#else

#define RIN "%lld"

#endif

#define ll long long

template <typename T>inline void read(T &res){

    T k=1,x=0;char ch=0;

    while(ch<'0'||ch>'9'){if(ch=='-')k=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    res=k*x;

}

const ll mod=10007;

ll jiec[10010],niy[10010];

ll n,m;

void exgcd(ll a,ll b,ll &x,ll &y){

    if(b==0){

        x=1,y=0;

        return ;

    }

    ll x0,y0;

    exgcd(b,a%b,x0,y0);

    x=y0;

    y=x0-(a/b)*y0;

}

ll inverse(ll a){

    ll x,y;

    exgcd(a,mod,x,y);

    return (x%mod+mod)%mod;

}

void init(){

    jiec[0]=niy[0]=1;

    for(int i=1;i<mod;i++) jiec[i]=jiec[i-1]*i%mod;

    niy[mod-1]=inverse(jiec[mod-1]);

    for(int i=mod-2;i>=1;i--) niy[i]=niy[i+1]*(i+1)%mod;

}

ll comb(ll a,ll b){

    return jiec[a]*niy[b]%mod*niy[a-b]%mod;

}

ll lucas(ll a,ll b){

    if(a<b) return 0;

    if(a==0&&b==0) return 1;

    if(a<mod&&b<mod) return comb(a,b);

    return lucas(a/mod,b/mod)*lucas(a%mod,b%mod)%mod;

}

void solve(){

    read(n),read(m);

    printf(RIN"\n",lucas(n,m));

}

int main(){

    init();

    int t;

    read(t);

    while(t--) solve();

    return 0;

}