卢卡斯定理(详细证明)

卢卡斯定理

- 问题
- 内容：
- 时间复杂度
- 证明
- - 给个定理：
  - 证明定理：
  - 再来个推论：
  - 所以我们就可以推出结论：
- 模板
- 题目
- - Luogu3807【模板】卢卡斯定理
  - P2480[SDOI2010]古代猪文(CRT+Lucas)

问题

求解取模组合数 $\binom nm\equiv x(mod ~p)$ ，其中 $n ， m$ 较大不适用于打表找阶乘，模数p较小且为素数。

内容：

$\binom nm~mod~p=\binom {\lfloor\frac np\rfloor}{\lfloor\frac mp\rfloor}\binom{n~mod~p}{m~mod~p}~mod~p\\$

$\binom {n~mod~p}{m~mod~p}$ 中的两个数都小于p，直接用阶乘和阶乘的逆求解， $\binom {\lfloor\frac np\rfloor}{\lfloor\frac mp\rfloor}$ 可以继续用 $l u c a s$ 求解，当 $m = 0$ 的时候返回 $1$

这样一来 $p$ 的范围不能够太大,一般再 $10^5$ 左右。

时间复杂度

预处理阶乘， $O (f (p) + g (n) l o g n)$ 其中 $f (p)$ 求解组合数的复杂度， $g (n)$ 表示求一次 $\binom{n}{m}$ 的复杂度

证明

给个定理：

$\binom pm ~mod~p=[m=p~\vee~m=0]\\$

证明定理：

$\binom pm=\frac{p!}{m!(p-m)!}~mod~p\\ while~m\neq p~\&\&~m\neq0\\ p!~mod~p=0\\ \therefore \binom pm ~mod~p=[m=p~\vee~m=0]\\$

再来个推论：

$(a+b)^p=(\sum_{i=1}^p\binom pia^ib^{n-i})~mod~p\\ \because \binom pi ~mod~p=[i=p~\vee~i=0]\\ \therefore(a+b)^p=(a^p+b^p)~mod~p\\$

所以我们就可以推出结论：

$(1+x)^n~mod~p\\ (1+x)^{p\lfloor\frac np\rfloor}(1+x)^{n~mod~p}~mod~p\\ ---\\ ---\\ 对(1+x)^{p\lfloor\frac np\rfloor}~mod~p进行分析\\ ((1+x)^p~mod~p)^{\lfloor\frac np\rfloor}\\ \because(a+b)^p~mod~p=(a^p+b^p)~mod~p\\ \therefore((1+x)^p~mod~p)^{\lfloor\frac np\rfloor}=(1+x^p)^{\lfloor\frac np\rfloor}~mod~p\\ ---\\ ---\\ \therefore(1+x)^{p\lfloor\frac np\rfloor}(1+x)^{n~mod~p}~mod~p=(1+x^p)^{\lfloor\frac np\rfloor}(1+x)^{n~mod~p}~mod~p\\ kx^m=\binom nmx^m=\binom {\lfloor\frac np\rfloor}{\lfloor\frac mp\rfloor}(x^p)^{{\lfloor\frac mp\rfloor}}\binom{n~mod~p}{m~mod~p}x^{m~mod~p}=\binom {\lfloor\frac np\rfloor}{\lfloor\frac mp\rfloor}\binom{n~mod~p}{m~mod~p}x^m\\ \therefore\binom nm mod~p=\binom {\lfloor\frac np\rfloor}{\lfloor\frac mp\rfloor}\binom{n~mod~p}{m~mod~p}~mod~p\\$

模板

void init(int p) {f[0] = 1;for(int i=1; i<=p; i++) {f[i] = 1ll*i*f[i-1]%p;}
}
int qpow(int x, int y, int p) {int ans = 1;while(y) {if(y & 1) ans = 1ll*ans*x%p;x = 1ll*x*x%p;y >>= 1;}return ans;
} 
int C(int n, int m, int p) {if(n < m) return 0;int inv1 = qpow(f[m], p-2, p);int inv2 = qpow(f[n-m], p-2, p);return 1ll*f[n]*inv1%p*inv2%p;
}int lucas(int n, int m, int p) {if(n < m) return 0ll;if(n == 0) return 1ll;return 1ll*C(n%p, m%p, p)*lucas(n/p, m/p, p) % p;
}

题目

Luogu3807【模板】卢卡斯定理

题意&&思路：模板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int f[N]; 
void init(int p) {f[0] = 1;for(int i=1; i<=p; i++) {f[i] = 1ll*i*f[i-1]%p;}
}
int qpow(int x, int y, int p) {int ans = 1;while(y) {if(y & 1) ans = 1ll*ans*x%p;x = 1ll*x*x%p;y >>= 1;}return ans;
} 
int C(int n, int m, int p) {if(n < m) return 0;int inv1 = qpow(f[m], p-2, p);int inv2 = qpow(f[n-m], p-2, p);return 1ll*f[n]*inv1%p*inv2%p;
}int lucas(int n, int m, int p) {if(n < m) return 0ll;if(n == 0) return 1ll;return 1ll*C(n%p, m%p, p)*lucas(n/p, m/p, p) % p;
}
int main() {
#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endif  int t;cin >> t;while(t--) {int n, m, p;cin >> n >> m >> p;init(p);cout << lucas(n+m, n, p) << endl;}return 0;
}

P2480[SDOI2010]古代猪文(CRT+Lucas)

问题：
$g^{\sum_{k|n}C_n^k}~\%~mod\\$
解题思路：

用扩展欧拉定理转化成求解指数是多少， $\sum_{k|n}C_n^k~\%~\phi(mod)$

$\phi(mod)$ 不是素数，但 $\phi(mod)$ 是由多个一次素数组成，且素数较小，我么就用中国剩余定理(CRT)来分解一下 $\phi(mod)$ ，求 $C_n^k$ 在各个质数下的模数是多少。

但 $C_n^k~\%~p$ 中 $n ， k$ 较大，但 $p$ 较小，所以我们就用 $L u c a s$ 定理来求解。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 999911659;
const int Mod = mod-1;
const int N = 36000;
ll p[5] = {1, 2, 3, 4679, 35617};
ll f[N], a[20], ans;
void init(ll pp) {f[0] = 1;for(int i=1; i<=pp; i++) {f[i] = 1ll*i*f[i-1]%pp;}
}ll qpow(ll x, ll y, ll pp) {ll ans = 1;x %= pp;while(y) {if(y & 1) ans = ans * x % pp;x = x * x % pp;y >>= 1;}return ans % pp;
}ll C(ll n, ll m, ll pp) {if(n < m) return 0ll;ll inv1 = qpow(f[m], pp-2, pp);ll inv2 = qpow(f[n-m], pp-2, pp);return 1ll*f[n]*inv1%pp*inv2%pp;
}ll lucas(ll n, ll m, ll pp) {if(n < m) return 0ll;if(!n) return 1ll;return C(n%pp, m%pp, pp)*lucas(n/pp, m/pp, pp) % pp;
}void CRT() {for(int i=1; i<5; i++) {ll m = Mod/p[i];ll inv = qpow(m, p[i]-2, p[i]);ans = (ans + a[i]*m%Mod*inv%Mod)%Mod;}
}
int main() {
#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endif  ll n, g;cin >>n >> g;if(g % mod == 0) {cout << 0 << endl;return 0;}for(int i=1; i<5; i++) {init(p[i]);for(int j=1; 1ll*j*j<=n; j++) {if(n % j == 0) {a[i] = (a[i] + lucas(n, j, p[i])) % p[i];if(1ll*j*j != n) {a[i] = (a[i] + lucas(n, n/j, p[i])) % p[i];}}}}CRT();cout << qpow(g, ans, mod)%mod << endl;return 0;
}