卢卡斯定理

标签：lfloor frac 定理 rfloor times choose 卢卡斯 bmod

卢卡斯定理常用于求组合数，且质数模数 \(p\) 较小时的情况（常常与费马小定理结合使用，要是 \(p\) 不是质数直接上扩欧就可以了）。
那为什么要用卢卡斯定理？
因为虽然 \(p\) 是质数，但是如果 \(x>p\)，那么他俩不一定互质，所以 \(x\) 在模 \(p\) 意义下不一定存在逆元，那我们的组合数公式无法正常的求出，卢卡斯定理正是为了解决这种情况。
首先咱们仍然先上结论（咱们用的是递推式，还有另外一个形式）：

\[{n\choose m}={n\bmod p\choose m\bmod p}\times {\lfloor\frac{n}{p}\rfloor\choose\lfloor\frac{m}{p}\rfloor} \]

接下来证明（其实有两种方法，个人认为这一种比较简单，另一种请自行查阅）：
我们首先需要证明几个引理。

引理 \(1\)：

\[\forall x\in[1,p)\cap\mathbb{Z},{p\choose x}\equiv 0\pmod p \]

其中 \(p\) 为质数。

证明

\[{p\choose x}=\frac{p!}{x!\times (p-x)!}=\frac{(p-1)!}{(x-1)!\times (p-x)!}\times\frac{p}{x}={p-1 \choose x-1}\times\frac{p}{x} \]

我们注意到 \(x<p\) 且 \(p\) 为质数，所以 \(\gcd(x,p)=1\)，那么 \(x\) 在模 \(p\) 意义下存在逆元，所以原式转化为：

\[{p-1\choose x-1}\times x^{-1}\times p\equiv 0\pmod p \]

得证。

引理 \(2\)：

\[(1+x)^p\equiv 1+x^p\pmod p \]

其中 \(p\) 仍然满足上述条件。

证明

二项式定理展开得（注意可以把其中的 \(1\) 省略）：

\[(1+x)^p=\sum_{i=0}^{p}{p\choose i}\times x^i \]

注意到根据引理 \(1\)，除了 \(i=0\) 和 \(i=p\) 时，所有的 \({p\choose i}\times x^i\) 都可以被 \(p\) 整除，所以咱们将 \(i=0\) 和 \(p\) 的时候单独拎出来，也就是 \(1+x^p\)，得证。

接下来可以愉快地证明卢卡斯定理了。

我们将最开始的 \(n,m\) 分解，变成 \(n=\lfloor\frac{n}{p}\rfloor\times p+(n\bmod p),m=\lfloor\frac{m}{p}\rfloor\times p+(m\bmod p)\)，其中 \(p\) 是题目中给的质数，那我们不妨令 \(l=\lfloor\frac{n}{p}\rfloor,r=\lfloor\frac{m}{p}\rfloor,w=n\bmod p,y=m\bmod p\)，则 \(n=l\times p+w,m=r\times p +y\)。
那么我们考虑用不同的方式表达出 \((1+x)^n\) 以寻求某些等量关系。
首先很正常的二项式定理：

\[(1+x)^n=\sum_{k=0}^{n}{n\choose k}\times x^k \]

我们不妨把 \(n\) 变一变：

\[(1+x)^n=(1+x)^{l\times p+w} \]

那么根据引理 \(2\) 有：

\[(1+x)^{l\times p + w}\equiv(1+x^p)^l\times (1+x)^w=(\sum_{i=0}^{l}{l\choose i}\times x^{p\times i})\times (\sum_{j=0}^{w}{w\choose j}\times x^j) \]

所以：

\[\sum_{k=0}^{n}{n\choose k}\times x^k=(\sum_{i=0}^{l}{l\choose i}\times x^{p\times i})\times (\sum_{j=0}^{w}{w\choose i}\times x^i) \]

在这里我们考虑 \(x\) 的指数是 \(m\) 时会发生什么，注意到当左边的 \(k\) 取 \(m\) 时，右边有且仅有唯一的 \(i\) 和 \(j\) 使得 \(p\times i+j=m\)（观察发现对于右边的每一项，\(x\) 的指数都是 \(p\times i +j\)）（想一想，为什么？），所以 \(i=r,j=y\)。既然是唯一的（也就是说不可能在其他时候 \(x\) 的指数再次是 \(m\)），则他们的系数也必须相等才能使得等号成立，那么咱们单独把系数拎出来搞一个等式。

\[{n\choose m}={l\choose r}\times {w\choose y} \]

其实就是：

\[{n\choose m}={\lfloor\frac{n}{p}\rfloor\choose\lfloor\frac{m}{p}\rfloor}\times{n\bmod p\choose m\bmod p} \]

然后我们就莫名其妙地得证了。

标签：lfloor,frac,定理,rfloor,times,choose,卢卡斯,bmod
From： https://www.cnblogs.com/Tomoyuki-Mizuyama/p/18363830