Lucas板子

发表于 | 分类于 |

适用于mod数较小，而实际计算时需要的阶乘数较大时，只需预处理出mod数范围内的阶乘即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll Cal(ll u, ll d, ll i)
{
    if (d < u)//注意返回0
        return 0;
    if (d == 0||d==u)
        return 1;
    return ((jc[d][i] * jc_inv[u][i] % mod[i]) * jc_inv[d - u][i])%mod[i];
}
ll Lucas(ll u, ll d, ll i)
{
    if (d < u)//注意返回0
        return 0;
    if (d == 0||d==u)
        return 1;
    
    return ((Lucas(u / mod[i], d / mod[i], i) % mod[i]) * Cal(u % mod[i], d % mod[i], i)) % mod[i];
}