卢卡斯定理

标签：lfloor dbinom 定理 rfloor 卢卡斯 bmod

多项式，就是提供了一个代数手段解决问题。——rsy

对于组合数模质数 \(p\) 问题，当 \(n,m\) 较大，\(p\) 较小的时候（\(n \ge p\)），有可能会出现 \(n!\) 没有逆元的情况。那么怎么处理这样的情况呢？这时候需要使用卢卡斯定理。

卢卡斯定理的内容：

\[\dbinom{n}{m} \bmod p = \dbinom{\lfloor\cfrac{n}{p}\rfloor}{\lfloor\cfrac{m}{p}\rfloor} \times \dbinom{n \bmod p}{m \bmod p}\bmod p \]

也有另一个形式（展开之后的）：将 \(n,m\) 拆位，假设从低到高有 \(0,...,k\) 位，那么

\[\dbinom{n}{m} \bmod p = \dbinom{n_0}{m_0} \times \dbinom{n_1}{m_1} \times ..., \dbinom{n_k}{m_k}\bmod p \]

证明：
首先有一个重要恒等式：
\((a + b)^p \bmod p = (a^p + b^p) \bmod p\)
这里的 \(p\) 不一定为素数。证明：

\[(a + b)^ p = \sum \limits_{i = 0}^p \dbinom{p}{i}a^p b^{n - p} \]

又

\[\dbinom{p}{i} = \cfrac{p!}{i!(p-i)!} \]

当 \(i = 0\) 或 \(i = p\) 的时候分子才有 \(p\) 的因子，因此

\[\dbinom{p}{i} \bmod p= [i = 0 \operatorname{or} i =p] \]

因此 \((a+b)^p\) 也只有 \(0,p\) 这两项是有贡献的。注意推导过程没有用到费马小定理，因此 \(p\) 可以是任意数。

然后的证明凸显了多项式的巧妙。这里引入 \([k]\operatorname{poly} x\) 的记号，\(\operatorname{poly} x\) 表示关于 \(x\) 的多项式。这个记号表示多项式里 \(k\) 的系数。

我们要求 \(\dbinom{n}{m}\) 的取值，就相当于求 \([x^m](1 + x)^n\)。考虑

\[(1+x)^n = (1 + x)^{p\lfloor\frac{n}{p}\rfloor}(1+x)^{n \bmod p} \equiv (1 + x^{p})^{\lfloor\frac{n}{p}\rfloor}(1+x)^{n \bmod p} \]

那么

\[[x^m](1+x)^n = [x^m](1 + x^{p})^{\lfloor\frac{n}{p}\rfloor}(1+x)^{n \bmod p} \\1 \]

标签：lfloor,dbinom,定理,rfloor,卢卡斯,bmod
From： https://www.cnblogs.com/Zeardoe/p/16994426.html