组合数方式3：

使用范围,应用条件：

c[a][b] % mod 中a,b很大(1 <=  a ,b <= 10 ^ 18)，但是mod的值不是很大(1 <= mod <= 10 ^ 5)

时间复杂度：

n * p * log[p][a] * log[2][p];  //其中n为计算c[a][b]的次数 //当p很大时，log[p][a]很小，如log[10 ^ 5][10 ^ 18] 近似为3~4

原理：

c[a][b] = c[a % mod][b % mod] + c[a / mod][b / mod];

代码实现：

int qmi(int a, int b , int mod)
{
    int res = 1 % mod;
    while(b)
    {
        if(b & 1)
        {
            res = (long long)res * a % mod;
        }
        b >>= 1;
        a = (long long)a * a % mod;
    }
    return res;
}

int c(int a,int b)
{
    int res  = 1;
    for(int i = 1 , j = a ; i <= b ; i++ , j--)
    {
        res = (long long)res * j % mod;
        res = (long long)res * qmi(i,mod - 2,mod) % mod;
    }
    return res;
}

int lucas(long long a, long long b, int mod)
{
    if(a < mod && b < mod)  //且要注意： a 不能等于 mod , b 不能等于 mod
    {
        return c(a,b) % mod;
    }
    return (long long)c(a % mod ,b % mod) * lucas(a / mod , b / mod , mod) % mod;
}