在数论中,Lucas定理用于计算二项式系数({ binom {m}{n}})被质数(p)除的所得的余数。
描述
设(p)为素数,(a,bin N_+),且
这里(0leq a_i,b_ileq p-1igwedge a_i,b_iin Z(i=0,1,2,3,cdots,k))
则有:
等价形式
由于
有
又因为(a_0<p),故
同理
故
又因为(a_0<p),故
同理
故
故
我们真正要用的,就是
证明
对于素数(n)和(m),满足(1le mle n-1), 二项式系数(C^m_n=frac{n!}{(n-m)!cdot m!}=frac{n(n-1)cdots(n-m+1)}{m(m-1)cdots1})可被(n)整除。由此可得,在母函数中
对于非负整数(i),若((1+x)^{p^{i}}equiv 1+x^{p^{i}}{pmod {p}})对于(ile t(tge 1))时成立,则有$$(1+x){p{t+1}}=(1+x){p{t} imes p}=((1+x){pt})p=1+x{p imes pt}=1+x{p^{t+1}}$$
对于任意非负整数(i),都有((1+X)^{p^{i}}equiv 1+X^{p^{i}}{pmod {p}})
故对于任意非负整数(m)和素数(p),将(m)用(p)进制表示,即$$m=sum _{i=0}{k}m_{i}p{i},$$其中(kin N_+)、(m_i)为整数且(0le m_ile p-1)。
又有:
此即证明了本定理。
看到评论区有人说看不懂最后一步,这里做一点解释:
- 第一行到第二行不用解释了吧。
- 第二行到第三行上面证明了。
- 第三行到第四行用的是二项式定理展开。
- 第四行到第五行由于(m_ile p-1),所以到(m_i)之后组合数的值都是(0),就都可以忽略了。
- 第五行到第六行发现(n_i)从(0sim p-1)都跑了一遍,把乘号展开,发现每一位从(0sim p-1)都出现了,全部组合后组合出了(0sim m)之间的所有数,故可得上式。
所以代码如下
typedef long long LL;
LL mod;
inline LL pow(LL a, LL b)//快速幂是为了求逆元
{
LL ans = 1;
for(; b; b >>= 1,a = a * a % mod)
if(b & 1)
ans = ans * a % mod;
return ans;
}
LL farc[1000005];
inline void prepare(LL a)
{
farc[0]=1;
for(LL i = 1; i <= a; ++i)
farc[i]=farc[i-1]*i%mod;
}
inline LL Csmall(LL m, LL n) // C(m,n) = (n!)/(m!*(n-m)!)
{
if(n < m)
return 0;
return farc[n] * pow(farc[m], mod-2) % mod * pow(farc[n-m], mod-2) % mod; // 费马小定理求逆元
}
inline LL C(LL m, LL n)
{
if(n < m)
return 0;
if(!n)
return 1;//Lucas的边界条件
return C(m/mod, n/mod) % mod * Csmall(m%mod, n%mod) % mod; // 上面证明的Lucas定理
}
一点联想
在做luogu P3937 Changing的时候,里面要大量计算组合数的奇偶性,那如何快速计算呢?我想到了一个简单的方法。
要算(C_n^m)的奇偶性,也就是要算(C_n^mmod 2)的值。由于(2)是质数,所以我们可以用Lucas转化成(prod C_{a_i}^{b_i} mod 2)的形式,其中(a_i)是(n)在二进制下的某一位,(b_i)是(m)在二进制下的某一位。由于(a_i, b_i)只能是(0)或(1),也就是说(C_{a_i}^{b_i})仅有(C_0^0, C_1^1, C_0^1, C_1^0)这几种形式,而其中只有(C_0^1)是(0),其余都是(1)。所以如果(n)在某一位是(0),而(m)在某一位是(1)的话,(C_n^m)就是偶数。那不就只要判一下(n ext{ and } m)就可以了吗?因此我们有:如果(n ext{ and }m = m),那么(C_n^m)是奇数,否则就是偶数。