多项式,就是提供了一个代数手段解决问题。——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\) 不一定为素数。证明:
又
\[\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