二项式定理

若

n

是正整数，则有：

\begin{aligned} (x+y)^n = \sum_{i=0}^n C_{n}^{i} x^i y^{n-i} \end{aligned}

。

用数学归纳法证明：

当

n=1

时原式显然成立。

假设

n=k

时原式成立，则

n=k+1

时，有：

\begin{aligned} (x+y)^{k+1} &= (x+y)(x+y)^k \\ &=(x+y) \sum_{i=0}^{k}C_{k}^{i} x^i y^{k-i} \\ &=(x+y) (C_k^0 y^k+C_k^1 x y^{k-1}+\dots+C_k^{k-1}x^{k-1}y+C_k^k x^k) \\ &=x^{k+1} + y^{k+1} + (C_k^0+C_k^1)xy^k+(C_k^1+C_k^2)x^2y^{k-1}+\dots+(C_k^{k-1}+C_k^k)x^ky \\ &= x^{k+1} + y^{k+1} + \sum_{i=1}^k (C_k^{i-1}+C_k^{i})x^i y^{k-i+1} \end{aligned}

因为

\begin{aligned} C_k^{i-1}+C_k^{i} &= \frac{k!}{(i-1)!(k-i+1)!} +\frac{k!}{i!(k-i)!} \\ &= \frac{k!\:i!\:(k-i)!+k!\:(i-1)!\:(k-i+1)!}{i! \: (i-1)! \: (k-i)! \: (k-i+1)!} \\ &= \frac{(k+1)!}{i! (k-i+1)!} \\ &= C_{k+1}^i \end{aligned}

所以

\begin{aligned} (x+y)^{k+1} &= x^{k+1} + y^{k+1} + \sum_{i=1}^k C_{k+1}^ix^i y^{k-i+1} \\ &=\sum_{i=0}^{k+1}C_{k+1}^ix^i y^{k-i+1} \end{aligned}

因此

n=k+1

时原式也成立，得证。

一个引理

若

p

是素数，则有：

(x+y)^p \equiv x^p + y^p \pmod p

。

证明：由二项式定理可知：

\begin{aligned} (x+y)^p = \sum_{i=0}^p C_{p}^{i} x^i y^{p-i} \end{aligned}

。

其中当

1 \le i < p

时：

\begin{aligned} C_p^i &= \frac{p!}{i!(p-i)!} \\ &= \frac{p\times(p-1)!}{i \times (i-1)!(p-i)!} \\ &= \frac{p}{i} C_{p-1}^{i-1} \end{aligned}

所以

\begin{aligned} C_p^i & \equiv \frac{p}{i} C_{p-1}^{i-1} \\ & \equiv \frac{p}{i} C_{p-1}^{i-1} \times i \times inv(i)\\ & \equiv p \times inv(i) C_{p-1}^{i-1} \\ & \equiv 0 \pmod p \end{aligned}

其中

inv(i)

表示

i

在模

p

意义下的乘法逆元。因为

p

是素数且

i < p

，故

inv(i)

一定存在。

原式在同余式中只剩下

i=0,p

两项，得证。

Lucas 定理

若

p

是素数，则有：

C_n^m \equiv C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \times C_{n \bmod p}^{m \bmod p} \pmod p

。

证明：

根据带余除法，令

n=ap+b,m=cp+d

，其中

0 \le b,d < p

。

根据二项式定理得到式子一：

(1+x) ^n \equiv \sum_{i=0}^{n} C_n^i x^i \pmod p

根据二项式定理和引理得到式子二：

\begin{aligned} (1+x) ^n &\equiv (1+x)^{ap+b} \\ &\equiv ((1+x)^p)^a\times(1+x)^b\\ &\equiv (1+x^p)^a \times(1+x)^b \\ &\equiv (\sum_{i=0}^a C_a^i x^{ip})(\sum_{j=0}^b C_b^j x^j) \pmod p \end{aligned}

由式子一可知

x^m

的系数为

C_n^m

。

由式子二可知

x^m=x^{cp+d}

的系数为

C_a^c C_b^d

。

因为

\lfloor \frac{n}{p} \rfloor = a ,\lfloor \frac{m}{p} \rfloor = c,n \bmod p =b,m \bmod p=d

。

所以

C_n^m \equiv C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \times C_{n \bmod p}^{m \bmod p} \pmod p

，证毕。

我们发现在求

C_n^m \bmod p

时不太好求，因为是两个很大的数相除，得转换成乘的形式。

因为

p

是素数，根据费马小定理：

m!^{p-1} \equiv 1 \pmod p,(n-m)!^{p-1} \pmod p

。

那么有：

C_n^m=\frac{n!}{m!(n-m)!} \equiv n! \times m!^{p-2} \times (n-m)!^{p-2} \pmod p

但是这样求是有一点问题的，因为

m!

或者

(n-m)!

可能是

p

的倍数，就不能用费马小定理了。

其实具体实现是可以避免的，因为在求

C_{n \bmod p}^{m \bmod p} \pmod p

时费马小定理是肯定成立的，可以直接求。

C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \pmod p

虽然没法直接求，但是可以利用 Lucas 定理进一步拆开，直到都能够拆成可求解的形式即可。

Code

CPP

#include <stdio.h>
#define int long long
int f[100005];
void init(int a,int p){ //求阶乘，f[i]=i!
	f[0]=f[1]=1;
	for(int i=2;i<=a;++i)
		f[i]=(f[i-1]*i)%p;
}
int pow(int a,int b,int p){  //快速幂
	a%=p;
	int res=1;
	while(b>0){
		if(b&1ll) res=(res*a)%p;
		a=(a*a)%p;
		b>>=1ll;
	}
	return res;
}
int C(int m,int n,int p){
	if(m>n) return 0;
	return (f[n]*pow(f[m],p-2,p)%p *pow(f[n-m],p-2,p))%p; //利用费马小定理求C
}
int Lucas(int m,int n,int p){
	if(!m) return 1;
	return C(m%p,n%p,p)*Lucas(m/p,n/p,p)%p;
  //m%p、n%p时可以直接求，m/p、n/p时可能不满足费马小定理则继续递归拆解
}
signed main(){
	int T; scanf("%lld",&T);
	while(T--){
		int n,m,p; scanf("%lld%lld%lld",&n,&m,&p);
		init(n+m,p);
		printf("%lld\n",Lucas(n,n+m,p));
	}
}

题解：P3807 【模板】卢卡斯定理/Lucas 定理

文章操作