[学习笔记]组合数取模的几种求法

2019-04-13 15:48发布

站内文章 / 模拟电子
14830 0 1173

一、引入

给定 nn ， mm ， pp ，求：
(nm) mod pinom nmmod p
其中 (nm)inom nm 为组合数，表示 nn 个元素中选出 mm 个的方案数。
即：
(nm)=n!m!×(n−m)!inom nm=frac{n!}{m! imes(n-m)!}
特殊地，我们规定 (n0)=1inom n0=1 且当 n<mn<m 时 (nm)=0inom nm=0 。

二、 n,m≤3,000n,mle 3,000

(nm)=(n−1m)+(n−1m−1)inom nm=inom {n-1}m+inom{n-1}{m-1}
（1）组合意义：
考察 nn 个元素中的最后一个元素是否被选出。
如果没有被选出，那么前面的 n−1n-1 个元素必须选出 mm 个，即 (n−1m)inom {n-1}m 。
如果被选出，那么前面的 n−1n-1 个元素必须选出 m−1m-1 个，即 (n−1m−1)inom {n-1}{m-1} 。
（2）数学推导：
(n−1m)+(n−1m−1)=(n−1)!m!×(n−1−m)!+(n−1)!(m−1)!×(n−m)!inom{n-1}m+inom{n-1}{m-1}=frac{(n-1)!}{m! imes(n-1-m)!}+frac{(n-1)!}{(m-1)! imes(n-m)!}
=(n−1)!×(n−m)+(n−1)!×mm!×(n−m)!=n!m!×(n−m)!=(nm)=frac{(n-1)! imes(n-m)+(n-1)! imes m}{m! imes(n-m)!}=frac{n!}{m! imes(n-m)!}=inom nm
（3）生成函数：
根据二项式定理 (a+b)n=∑i=0n(ni)aibn−i(a+b)^n=sum_{i=0}^ninom nia^ib^{n-i} ，数列
(n0),(n1),(n2),...,(nn)inom n0,inom n1,inom n2,...,inom nn
的生成函数为 (1+x)n(1+x)^n 。
于是 (nm)inom nm 就是 (1+x)n(1+x)^n 的 mm 次项。
设 (F(x))k(F(x))_k 表示多项式 F(x)F(x) 的 kk 次项。
则：
(n−1m)+(n−1m−1)=((1+x)n−1)m+((1+x)n−1)m−1inom{n-1}m+inom{n-1}{m-1}=((1+x)^{n-1})_m+((1+x)^{n-1})_{m-1}
=((1+x)n−1)m+(x(1+x)n−1)m=((1+x)n)m=(nm)=((1+x)^{n-1})_m+(x(1+x)^{n-1})_m=((1+x)^n)_m=inom nm

热门文章