BZOJ 2982 combination

lucas定理裸题。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 20050
#define mod 10007
using namespace std;
long long t,n,m,inv1[maxn],inv2[maxn];
long long f_pow(long long x,long long y)
{
    long long ans=1,base=x;
    while (y)
    {
        if (y&1) ans=(ans*base)%mod;
        base=(base*base)%mod;
        y>>=1;
    }
    return ans%mod;
}
void get_table()
{
    inv1[0]=1;inv2[0]=10008;
    for (long long i=1;i<=10007;i++)
    {
        inv1[i]=inv1[i-1]*i%mod;
        inv2[i]=f_pow(inv1[i],mod-2);
    }
}
long long comb(long long n,long long m)
{
    return inv1[n]*inv2[m]%mod*inv2[n-m]%mod;
}
long long lucas(long long n,long long m)
{
    if (!m) return 1;
    return comb(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
}
int main()
{
    get_table();
    scanf("%lld",&t);
    for (long long i=1;i<=t;i++)
    {
        scanf("%lld%lld",&n,&m);
        printf("%lld
",lucas(n,m));
    }
    return 0;
}