组合数取模（lukas）板子

求 C(n,m)%mo

#include<bits/stdc++.h>
#define re register int
#define mo 10007
#define ll long long
#define N 200000010
using namespace std;
ll t;
ll inv(ll d,ll z)
{
    ll ans=1;
    while(z)
    {
        if(z&1)
            ans=ans*d%mo;
        z>>=1;
        d=d*d%mo;
    }
    return ans;
}
ll C(ll a,ll b)
{
    if(a<b)
        a+=mo;
    ll up=1,down=1;
    for(re i=a-b+1;i<=a;i++)
        up=up*i%mo;
    for(re i=2;i<=b;i++)
        down=down*i%mo;
    return up*inv(down%mo,mo-2)%mo;
}
ll lucas(ll n,ll m)
{
    if(m>n)
        return 0;
    if(m==0||n==0)
        return 1;
    return lucas(n/mo,m/mo)*C(n%mo,m%mo)%mo;
}
int main()
{
    scanf("%lld",&t);
    ll m,n;
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",lucas(n,m));
    }
    return 0;
}

组合数取模（lukas）板子

原文：https://www.cnblogs.com/WindZR/p/14726039.html