本文主要介绍组合数(combinatorial number),及其取模运算的技巧。

前置知识

组合数

在一个 nn 元集合每次选出 mm (0mn)(0 \le m \le n) 个不同的元素,不管其顺序,称为从 nn 个元素中不重复地选取 mm 个元素的一个组合。所有这样的组合的种数称为组合数。写作 (nm)\binom{n}{m}CnmC_{n}^{m}

计算公式
Cnm=PnmPm=n!m!(nm)!=nmm!  ,  Cn0=1C_{n}^{m} = \frac{P^{m}_{n}}{P_{m}}=\frac{n!}{m!(n-m)!}=\frac{n^{\underline m}}{m!} ~~,~~ C^{0}_{n}=1
互补性质

nn 个不同元素中取出 mm 个元素的组合数 ==nn 个不同元素中取出 nmn-m 个元素的组合数,即:

(nm)=(nnm)\binom{n}{m}=\binom{n}{n-m}
组合恒等式
(nm)=(nm1)=(n1m1)+(n1m)\binom{n}{m}=\binom{n}{m-1}=\binom{n-1}{m-1}+\binom{n-1}{m}

其组合意义为:固定一个特殊元素,则选出的 mm 的元素中可以包含 (n1m1)\binom{n-1}{m-1} 或不包含 (n1m)\binom{n-1}{m} 这个元素。

Lucas 定理

nn , mm (nmn \leq m) 在 pp(一个素数) 进制下可以分别表示成 nknk1...n0p\overline{n_{k}n_{k-1}...n_{0}}_{p}mkmk1...m0p\overline{m_{k}m_{k-1}...m_{0}}_{p},则

(nm)i=0k(nimi) (mod p)\binom{n}{m} \equiv \prod_{i=0}^{k} \binom{n_{i}}{m_{i}} ~ (\text{mod} ~ \text{p})

证明: (ab)=(a1m1)×ab\binom{a}{b}=\binom{a-1}{m-1}\times \frac{a}{b} ,借助二项式定理,有

(1+x)pi=0n(pi)xi1+xp (mod p)(1+x)^{p} \equiv \sum_{i=0}^{n}\binom{p}{i} x^{i} \equiv 1+x^{p} ~ (\text{mod} ~ \text{p})

n=a1p+b1n=a_{1}p+b_{1}m=a2p+b2m=a_{2}p+b_{2} ,推出 (1+x)n(1+x)a1p×(1+x)b1(1+xp)a1×(1+x)b1 (mod p)(1+x)^{n} \equiv (1+x)^{a_{1}p} \times (1+x)^{b_{1}} \equiv (1+x^{p})^{a_{1}} \times (1+x)^{b_{1}} ~ (\text{mod} ~ \text{p})

其中等式两边 xmx^{m} 的系数分别为 (nm)(a1a2)×(b1b2) (mod p)\binom{n}{m} \equiv \binom{a_{1}}{a_{2}} \times \binom{b_{1}}{b_{2}} ~ (\text{mod} ~ \text{p}) 。得证。

相关题目



  • hdu4373 Mysterious For (找规律,Lucas定理,中国剩余定理)

    题意:有 mm 层循环,循环有两种类型

    1. for(int a [i] = 0; a [i] <n; a [i] ++){ ... }
    2. for(int a [i] = a [i - 1]; a [i] <n; a [i] ++){ ... }

    给出 kk 个类型 11 循环的位置,请求出最内层命令被执行的次数对 364875103364875103 取模的结果。 n,m106,k15n,m \leq 10^{6}, k \leq 15

    找规律可以发现,若第一种类型的循环下有 m1m-1 层第二种循环,那么答案为 Cn+m1mC_{n+m-1}^{m}364875103=97×3761599364875103=97 \times 3761599 ,所以分别计算 Cn+m1mC_{n+m-1}^{m} mod\text{mod} 77mod\text{mod} 37615993761599 的答案,用CRT合并就好了。
    Code: https://vjudge.net/solution/17871855


  • hdu4939 Xiao Ming's Hope (Lucas定理)

    题意:求 Cn0,Cn1,...,CnnC_{n}^{0}, C_{n}^{1}, ... , C_{n}^{n} 中奇数的个数,n108n \leq 10^{8}

    注意Lucas定理的形式,(nm)i=0k(nimi) (mod p)\binom{n}{m} \equiv \prod_{i=0}^{k} \binom{n_{i}}{m_{i}} ~ (\text{mod} ~ \text{p}) 。若 Cnk1 (mod 2)C_{n}^{k} \equiv 1 ~ (\text{mod}~2) ,任意的 0ik0 \leq i \leq k ,满足 (nimi)1 (mod 2)\binom{n_{i}}{m_{i}} \equiv 1 ~ (\text{mod} ~ \text{2})

    (00)=1,(01)=0,(10)=1,(11)=1\binom{0}{0}=1,\binom{0}{1}=0,\binom{1}{0}=1,\binom{1}{1}=1 ,所以当 nn 的二进制为 00 时,mi=0m_{i}=0 。答案为
    Code: https://vjudge.net/solution/17873375

组合数为奇数的一个性质:若 Cnm1 (mod 2)C_{n}^{m} \equiv 1 ~ (\text{mod} ~ 2) ,则 n&m=mn\&m=m


  • BZOJ1951 [Sdoi2010]古代猪文 (Lucas定理,中国剩余定理)

    题意:给出 N,G109N, G \leq 10^{9} ,求 GdNCNd (mod 999911659)G^{\sum_{d|N}C_{N}^{d}} ~ (\text{mod}~999911659)

    欧拉定理,GdNCNd (mod 999911659)GdNCNd mod 999911658 (mod 999911659)G^{\sum_{d \mid N}C_{N}^{d}} ~ (\text{mod}~999911659) \Leftrightarrow G^{\sum_{d \mid N}C_{N}^{d}~\text{mod}~999911658} ~ (\text{mod}~999911659)999911658=2×3×4679×35617999911658 = 2 \times 3 \times 4679 \times 35617,套 CRT 就好了。注意特判 G=999911659G=999911659 的情况。

    Code: https://vjudge.net/solution/17879541


补充

扩展 Lucas 定理

相关题目

参考资料