1.组合数 C n m C_n^m Cnm​是一类增长速度非常快的数， C 300 150 C_{300}^{150} C300150​就已经是一个90位的数了，当m，n取 1 0 9 10^9 109级别甚至更大的数时，其组合数肯定难以计算了，所以做题时常常会需要组合数对一个数取模。而卢卡斯定理在这种情况下就派上了用场。

2.卢卡斯定理的应用：在m，n很大的时候,快速求解 C n m % p C_n^m\%p Cnm​%p

3.卢卡斯定理的具体表述：

C n m = C a 0 b 0 ⋅ C a 1 b 1 ⋅ C a 2 b 2 ⋅ ⋅ ⋅ C a k b k C^m_n=C^{b_0}_{a_0}\cdot C^{b_1}_{a_1}\cdot C^{b_2}_{a_2}\cdot\cdot\cdot C^{b_k}_{a_k} Cnm​=Ca0​b0​​⋅Ca1​b1​​⋅Ca2​b2​​⋅⋅⋅Cak​bk​​(mod p) = ∏ i = 0 k C a i b i =\prod_{i=0}^{k} C^{b_i}_{a_i} =∏i=0k​Cai​bi​​ (mod p)

(mod p)表示只是在模p的条件下成立

其中 n = a 0 + a 1 p + a 2 p 2 + ⋅ ⋅ ⋅ + a k p k n=a_0+a_1p+a_2p^2+\cdot\cdot\cdot+a_kp^k n=a0​+a1​p+a2​p2+⋅⋅⋅+ak​pk, m = b 0 + b 1 p + b 2 p 2 + ⋅ ⋅ ⋅ + b k p k m=b_0+b_1p+b_2p^2+\cdot\cdot\cdot+b_kp^k m=b0​+b1​p+b2​p2+⋅⋅⋅+bk​pk

即将m，n按p进制展开

4.卢卡斯定理的等价式子：

这个式子和上面的式子是完全等价的，而且也是在编程中更常用的，因为可以通过函数递归来实现：

C n m = C n % p m % p ⋅ C n / p m / p C_n^m=C_{n\%p}^{m\%p}\cdot C_{n/p}^{m/p} Cnm​=Cn%pm%p​⋅Cn/pm/p​ ( mod p)

这里的/是向下取整的

证明很简单，和进制转换的模n取余法是一样的：

n = a 0 + a 1 p + a 2 p 2 + ⋅ ⋅ ⋅ + a k p k n=a_0+a_1p+a_2p^2+\cdot\cdot\cdot+a_kp^k n=a0​+a1​p+a2​p2+⋅⋅⋅+ak​pk

n%p即 a 0 a_0 a0​ ，因为多项式中其他的项都至少含有一个p，也就是p的倍数。

n/p即 a 1 + a 2 p + a 3 p 2 + ⋅ ⋅ ⋅ + a k p k − 1 a_1+a_2p+a_3p^2+\cdot\cdot\cdot+a_kp^{k-1} a1​+a2​p+a3​p2+⋅⋅⋅+ak​pk−1

不断重复上述过程即将， C n m C_n^m Cnm​转化成了卢卡斯定理表达的那样。

可以发现，在经过卢卡斯定理的化简后，我们只需要不断求 C n % p m % p C_{n\%p}^{m\%p} Cn%pm%p​即可，大大减小了运算量。

1.同余：

两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余。

记作：a≡b (mod m)，

2.证明 ( 1 + x ) p (1+x)^p (1+x)p≡ 1 + x p 1+x^p 1+xp(mod p) (前提：p为素数）

①将 ( 1 + x ) p (1+x)^p (1+x)p按二项式展开，得：

( 1 + x ) p = C p 0 x 0 + C p 1 x + C p 2 x 2 + C p 3 x 3 + ⋅ ⋅ ⋅ + C p k x k + ⋅ ⋅ ⋅ + C p p x p (1+x)^p=C^0_px^0+C^1_px+C^2_px^2+C^3_px^3+\cdot\cdot\cdot+C^k_px^k+\cdot\cdot\cdot+C^p_px^p (1+x)p=Cp0​x0+Cp1​x+Cp2​x2+Cp3​x3+⋅⋅⋅+Cpk​xk+⋅⋅⋅+Cpp​xp

其中 C p 0 x 0 = 1 , C p p x p = x p C^0_px^0=1, C^p_px^p=x^p Cp0​x0=1,Cpp​xp=xp

所以我们可以将这个式子写成:

1 + C p 1 x + C p 2 x 2 + C p 3 x 3 + ⋅ ⋅ ⋅ + C p k x k + ⋅ ⋅ ⋅ + x p 1+C^1_px+C^2_px^2+C^3_px^3+\cdot\cdot\cdot+C^k_px^k+\cdot\cdot\cdot+x^p 1+Cp1​x+Cp2​x2+Cp3​x3+⋅⋅⋅+Cpk​xk+⋅⋅⋅+xp

②由 C p i ( i ∈ [ 1 , n ] ) = p ! i ! ⋅ ( p − i ) ! C_p^i (i∈[1,n])=\frac{p!}{i!\cdot(p-i)!} Cpi​(i∈[1,n])=i!⋅(p−i)!p!​可得，当p为素数时，由于其分子中含有p,其必然是p的倍数，即 C p i C_p^i Cpi​%p==0。（注：若p为合数，则将被分母中的数约掉,这也解释了卢卡斯定理为什么要求p必须为素数）

所以除了第一项和最后一项（也就是1和 x p x^p xp）， ( 1 + x ) p (1+x)^p (1+x)p的二项展开式中其他几项都%p==0。

③同余相加定理：

若a≡b(mod m)，c≡d(mod m)，则a+c≡b+d(mod m)

因为 C p i C_p^i Cpi​%p=0 ，可以记为 C p i C_p^i Cpi​≡0 （mod p）

所以二项展开式中间的几项在%p的意义上其实相当于0

所以：

( 1 + x ) p (1+x)^p (1+x)p≡ 1 + x p 1+x^p 1+xp(mod p)

证毕

3.证明 C n m = C n % p m % p ⋅ C n / p m / p C_n^m=C_{n\%p}^{m\%p}\cdot C_{n/p}^{m/p} Cnm​=Cn%pm%p​⋅Cn/pm/p​ ( mod p)

注：上面的/是计算机意义上的除以，即舍弃余数（向下取整）

令n=sp+q ， m=tp+r

其中q，r就是n和m 除以p 的余数 而s，t就是n，m除以p后截断的部分（向下取整）

那么我们要证明的就是 C n m = C q r ⋅ C s t C_n^m=C_q^{r}\cdot C_{s}^{t} Cnm​=Cqr​⋅Cst​( mod p) :

对于 ( 1 + x ) n (1+x)^n (1+x)n, C n m C^m_n Cnm​就是其指数为 x m x^m xm的项的系数

① 先化简：

( 1 + x ) n = ( 1 + x ) s p + q = [ ( 1 + x ) p ] s ⋅ ( 1 + x ) q (1+x)^n=(1+x)^{sp+q}=[(1+x)^p]^s\cdot(1+x)^q (1+x)n=(1+x)sp+q=[(1+x)p]s⋅(1+x)q

②在同余意义下：

上 式 ≡ ( 1 + x p ) s ⋅ ( 1 + x ) q 上式≡(1+x^p)^s\cdot(1+x)^q 上式≡(1+xp)s⋅(1+x)q ( mod p)

③再将 ( 1 + x p ) s ⋅ ( 1 + x ) q (1+x^p)^s\cdot(1+x)^q (1+xp)s⋅(1+x)q二项式展开得：

[ 1 + C s 1 x p + C s 2 x 2 p + C s 3 x 3 p + ⋅ ⋅ ⋅ ] ⋅ [ 1 + C q 1 x + C q 2 x 2 + C q 3 x 3 + ⋅ ⋅ ⋅ ] [1+C^1_sx^p+C^2_sx^{2p}+C^3_sx^{3p}+\cdot\cdot\cdot]\cdot[1+C^1_qx+C^2_qx^2+C^3_qx^3+\cdot\cdot\cdot] [1+Cs1​xp+Cs2​x2p+Cs3​x3p+⋅⋅⋅]⋅[1+Cq1​x+Cq2​x2+Cq3​x3+⋅⋅⋅]

④现在我们要得到指数为 x m x^m xm的项的系数：

m=tp+r，所以 x m = x t p ⋅ x r x^m=x^{tp}\cdot x^{r} xm=xtp⋅xr,因为q是一个小于p的数，所以后一个多项式，即 ( 1 + x ) q (1+x)^q (1+x)q不可能提供指数大于p的项。同理，前一个多项式，即 ( 1 + x p ) s (1+x^p)^s (1+xp)s，不可能提供指数小于p的项。

所以， x m x^m xm的系数必然为前一个多项式中 x t p x^{tp} xtp的系数乘以后一个多项式的 x r x^{r} xr系数，也就是 C q r ⋅ C s t C_q^{r}\cdot C_{s}^{t} Cqr​⋅Cst​

⑤综上，得证 C n m = C n % p m % p ⋅ C n / p m / p C_n^m=C_{n\%p}^{m\%p}\cdot C_{n/p}^{m/p} Cnm​=Cn%pm%p​⋅Cn/pm/p​ ( mod p)

每次只要求 C n % p m % p C_{n\%p}^{m\%p} Cn%pm%p​，大大减少了计算量，至于这里的C就是计算组合数的函数

具体如下：