关于卢卡斯定理

关于卢卡斯定理Lucas

学习博客有点巧，学长在写这篇博客的时候机房在装修现在我在写机房也在装修233

内容：

$1.$我不知道这个是什么.....
$C_m^n=\prod_{i=0}^k C_{n_i}^{m^i}(mod \ p)$
$n=n_kp^k+n_{k-1}p^{k-1}+...+n_1p+n_0$
$m=k_kp^k+m_{k-1}p^{k-1}+...+m_1p+m_0$

$2.$但这个肯定是

$C_n^m \% p=(C_{n/p}^{m/p}\%p)*(C_{n\%p}^{m\%p})\%p$

做题什么的一般就用这个的

证明：

知识储备：二项式定理
由二项式定理可得：
$C_a^b$即为$(a+b)^a$中$x^b$的系数.
$\therefore$ 对于方程$(1+x)^{a_0}(1+x^p)^{a_1}......(1+x^{p^k})^{a_k} \ (mod \ p)$
$C_{a_0}^{b_0}$ 即为 $(a+x)^{a_0}$中$x^{b_0}$的系数
$C_{a_1}^{b_1}$即为$(a+x^{p^1})^{a_1}$中$x^{b_1p^1}$的系数
$.$
$.$
$.$
$C_{a_k}^{b_k}$即为$(a+x^{p^k})^{a_k}$中$x^{b_kp^k}$的系数
将$C_{a_0}^{b_0}x^{b_0},C_{a_1}^{b_1}x^{b_1p^1}...C_{a_k}^{b_k}x^{b_kp^k}$相乘
(这里我真的不知道为什么要乘起来，他就是要乘起来，)
可得：$C_{a_0}^{b_0}*C_{a_1}^{b_1}...C_{a_k}^{b_k}x^b$
又$\because b=b_kp^k+b_{k-1}p^{k-1}+...+b_1P^1+b_0$
$\therefore $ $C_a^b\equiv C_{a_0}^{b_0}*C_{a_1}^{b_1}......C_{a_k}^{b_k} \ (mod \ p)$
证毕.

$2$我不会证

应用：

应用于取值范围适中的情况就是不大不小的情况来一道例题感受一下

例题洛谷P3807 【模板】卢卡斯定理

这个题主要就是应用$2$注意除法的时候要转化成乘他的逆元

$Code:$

#include <cstdio>
#include <iostream>
#define int long long
using namespace std;
const int N = 100000;
int T, a[N], n, m, p;
int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();}
    while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
}
int inv(int x, int y, int p) {
    y = p - 2;
    int sum = 1;
    while(y) {
        if(y & 1) sum = (sum * x) % p;
        x = (x * x) % p;
        y >>= 1;
    }
    return sum;
}
int C(int n, int m) {
    if(m > n) return 0;
    return (a[n] * (inv(a[m], p - 2, p) % p) * (inv(a[n - m], p - 2, p))) % p;
}
int Lucas(int n, int m) {
    if(!m) return 1;
    return (Lucas(n / p, m / p) * (C(n % p, m % p) % p)) % p;
}
signed main() {
    T = read();
    a[0] = 1;
    while(T--) {
        n = read(), m = read(), p = read();
        for(int i = 1; i <= p; i++) a[i] = (a[i - 1] * i) % p;
        cout << Lucas(n + m, n) << endl;
    }
    return 0;
}

谢谢收看，祝身体健康！