卢卡斯定理与扩展卢卡斯定理

概念

卢卡斯定理要解决的问题很简单：
如果规定为质数，那么就用卢卡斯定理解决，否则就是扩展卢卡斯定理。
洛谷上两个模板题都有 Lucas ExLucas

前置知识

如果你不知道前置的知识的话，最好还是去系统学习一下。

1. 乘法逆元

若且与互质，则称的意义下的乘法逆元为

关于求逆元：
因为
所以
所以
所以的逆元为
直接快速幂就可以了。

2.扩展欧几里得

扩展欧几里得用来在求得的同时，找出整数使其满足

3.费马小定理

。

4.中国剩余定理

还请移步博客欧几里得与扩展中国剩余定理Excrt

卢卡斯定理

证明过程：
首先根据组合数的只是我们可以很显然推出 $

然后根据二项式定理得出：
然后我们继续从二项式定理推出：
上式也就是所谓的卢卡斯定理，这玩意的用处就在于下面这个递推式：
其中且
实际上就是一个费马小定理和乘法逆元。
根据这个东西就可以很快地求出来上面的问题了。
如果你看不大懂，那就只需要记结论。。。。

然后直接递归调用就可以了。
对于的除法取模就需要用到逆元了。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long LL ;
const int MAXN = 100010 ;
LL N, M, P, X[MAXN] ;

inline LL Read() {
    LL X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
    return X * F ;
}

inline LL QuickPow(LL A, LL B) {
    LL Ans = 1 ;    if (! B) return 1 % P ;
    while (B) {
        if (B & 1) Ans = Ans * A % P ;
        A = A * A % P, B >>= 1 ;
    }    return Ans ;
}

inline LL C(LL A, LL B) {
    if (B > A) return 0 ;
    return (X[A] * QuickPow(X[B], P - 2)) % P * QuickPow(X[A - B], P - 2) % P ;
}

inline LL Lucas(LL A, LL B) {
    if (! B) return 1 ;
    else return (C(A % P, B % P) * Lucas(A / P, B / P)) % P ;
}

int main() {
    int T = Read() ; while (T --) {
        N = Read(), M = Read(), P = Read() ;
        X[0] = 1 ;
        for (LL i = 1 ; i <= P ; i ++) 
            X[i] = (X[i - 1] * i) % P ;
        LL Ans = Lucas(N + M, N) ; 
        printf("%lld\n", Ans) ;
    }    return 0 ;
}

扩展卢卡斯定理

令
假设我们知道就可以直接上，但是我们并不知道。（泪目
怎么求呢？
对于
我们可以阶乘的变换。
假设我们现在要求
我们将中所有的倍数拿出来合并。
那么我们就得到个满足项，然后除以之后，就得到,这一部分不好算，我们直接递归下去。
然后对于其他的项，可以看出来他们具有小于的循环节这种东西，就可以暴力。
然后时间复杂度就很可观了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>

#define int LL

using namespace std ;

typedef long long LL ;
const int MAXN = 1000010 ;
const int MAXM = 1000010 ;
const int Inf = 0xfffffff ;

int N, M, P, Ans ;

inline int Read() {
    int X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
    return X * F ;
}

inline int Exgcd(int A, int B, int & X, int & Y) {
    if (B == 0) {X = 1, Y = 0 ; return A ;}
    int R = Exgcd(B, A % B, X, Y) ;
    int F = X ; X = Y ; Y = F - A / B * Y ;
    return R ;
}

inline int Quick_Pow(int A, int B, int Mod) {
    int Ans = 1 ;
    while (B) {
        if (B & 1) Ans = Ans * A % Mod ;
        A = A * A % Mod ; B >>= 1 ;
    }    return Ans ;
}

inline int Fac(int Now, int A, int B) {
    if (! Now) return 1 ; int Ans = 1 ;
    for (int i = 2 ; i <= B ; i ++) 
        if (i % A) Ans = Ans * i % B ;
    Ans = Quick_Pow(Ans, Now / B, B) ;
    for (int i = 2 ; i <= Now % B ; i ++)
        if (i % A) Ans = Ans * i % B ;
    return Ans * Fac(Now / A, A, B) % B ;
}

inline int Inv (int Now, int Mod) {
    int X, Y ;
    Exgcd(Now, Mod, X, Y) ;
    if ((X += Mod) > Mod) return X - Mod ;
    else return X ;
}

inline int C (int n, int m, int A, int B) {
    int F = Fac(n, A, B), R = Fac(m, A, B) ;
    int L = Fac(n - m, A, B), Ans = 0, k = n - m ;
    for (int i = n ; i ; i /= A) Ans += i / A ;
    for (int i = m ; i ; i /= A) Ans -= i / A ;
    for (int i = k ; i ; i /= A) Ans -= i / A ;
    return F * Inv(R, B) % B * Inv(L, B) % B * 
           Quick_Pow(A, Ans, B) % B ;
}

inline int Crt(int Now, int Mod) {
    return Now * Inv(P / Mod, Mod) % P * (P / Mod) % P ;
}

signed main () {
    N = Read(), M = Read(), P = Read() ; 
    int B,PP = P ;
    for(int i = 2 ; i <= sqrt(P) + 5 ; i ++)
        if (PP % i == 0) {
            B = 1 ;
            while (PP % i == 0)
                B *= i, PP /= i ;
            Ans = Ans + (Crt(C(N, M, i, B), B) % P) ;
        }
    if (PP > 1) Ans = Ans + (Crt(C(N, M, PP, PP), PP) % P) ;
    printf("%lld\n", Ans % P) ;
    return 0 ;
}