[AcwingXLuogu] 卢卡斯定理/Lucas 定理 模板的使用

前言

luogu传送门 : Acwing传送门 :

思路

首先给出卢卡斯定理 (就是将求 C ( a , b ) C(a,b) C(a,b)分而治之) C a b ≡ C a % p b % p ∗ l u c a s a p b p (   m o d   p ) C_{a}^{b} \equiv C_{a \% p}^{b \% p} * lucas_{\frac{a}{p}}^{\frac{b}{p}}(\bmod p) Cab​≡Ca%pb%p​∗lucaspa​pb​​(modp)

显然的 : 我们左边 C C C是需要求的 而右边 l u c a s lucas lucas是通过递归求解 那么左边如何求呢 ? C a b = a ! ( a − b ) ! ∗ b ! = a ∗ ( a − 1 ) ∗ ( a − 2 ) ∗ … ∗ ( a − b + 1 ) ∗ ( a − b ) ∗ … ∗ 1 ( a − b ) ∗ ( a − b − 1 ) ∗ … ∗ 1 ∗ b ! = a ∗ ( a − 1 ) ∗ ( a − 2 ) ∗ … ( a − b + 1 ) b ! C_{a}^{b}=\frac{a !}{(a-b) ! * b !}=\frac{a *(a-1) *(a-2) * \ldots *(a-b+1) *(a-b) * \ldots * 1}{(a-b) *(a-b-1) * \ldots * 1 * b !}=\frac{a *(a-1) *(a-2) * \ldots(a-b+1)}{b !} Cab​=(a−b)!∗b!a!​=(a−b)∗(a−b−1)∗…∗1∗b!a∗(a−1)∗(a−2)∗…∗(a−b+1)∗(a−b)∗…∗1​=b!a∗(a−1)∗(a−2)∗…(a−b+1)​

我们通过化简可以发现,最后会化简成 每次 ∗ a 并 且 / b *a 并且 /b ∗a并且/b 因此,我们可以通过一层循环

直接求,同时因为需要牵扯到除法取模运算,我们还需要用快速幂求一次逆元

时间复杂度 O ( p + l o g p N ) O(p+log_pN) O(p+logp​N)

遗留的问题 : 为什么右边不可以也用组合数求解,而是选择递归的求

CODE

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}


int C(int a, int b, int p)
{
    if (b > a) return 0;

    int res = 1;
    for (int i = 1, j = a; i > a >> b >> p;
        cout