Lucas定理
内容
对于一个组合数$C_m^n$,取模一个素数$p$的值,假设$n=a\times p+b$,$m=c\times p+d$有:
$C_n^m≡C_a^c\times C_b^d(\mod p)$
证明
先证明一个一会儿要用到的定理:
$(1+x)^p≡1+x^p(\mod p)$
这里可以用费马小定理加以证明:
由于$(1+x)^p≡(1+x)(\mod p)$
且$x^p≡x(\mod p)$即$1+x^p≡1+x(\mod p)$
于是得证:$(1+x)^p≡1+x^p(\mod p)$
然后设$n=a\times p+b$,$m=c\times p+d$
于是:$(1+x)^n≡(1+x)^{a\times p+b}(\mod p)$
即:
$(1+x)^n≡(1+x)^{a\times p}\times (1+x)^b(\mod p)$
由之前证明的定理得:
$(1+x)^{a\times p}≡(1+x^p)^a(\mod p)$
即:
$(1+x)^{a\times p+b}≡(1+x^p)^a\times (1+x)^ b(\mod p)$
由二项式定理得:
$(1+x)^{a\times p+b}≡\displaystyle \sum^{i\to a}{i=0}(C_a^i\times x^{p\times i})\times \displaystyle \sum^{j\to b}{j=0}(C_b^j\times x^j)(\mod p)$
考虑等号两边$x^m$的系数:
由二项式定理得左边$x^m$的系数为:$C_n^m$
将右边的式子展开,显然当i,j满足$p\times i+j==m$时为$x^m$的系数,也就是$i==c,j==d$时,也就是:
$C_a^c\times C_b^d$
则能得到等式$C_n^m≡C_a^b\times C_b^d(\mod p)$
于是定理得到了证明。
代码
1 |
|
拓展Lucas定理
考虑如果p不是素数的情况,我们考虑利用唯一分解定理将p分解为若干素数的乘积,于是可以将式子分解为一组方程组,即:
$C_n^m≡r_1(\mod p_1)$
$C_n^m≡r_2(\mod p_2)$
$C_n^m≡r_3(\mod p_3)$
.
.
.
$C_n^m≡r_k(\mod p_k)$
于是这个方程组又让我们想到了中国剩余定理(CRT),于是我们就可以使用Lucas定理把$r_1…r_k$求出来,再用中国剩余定理求解$C_n^m$。
代码
1 |
|