组合数学详解

组合数学

1 基本概念

1. 加法原理和乘法原理

有4个基本的计数原理：加法原理、乘法原理、除法原理、减法原理。下面介绍加法原理和乘法原理。
(1) 加法原理：设集合S划分为 S 1 , S 2 , ⋯   , S m S_{1},S_{2},cdots,S_{m} S1​,S2​,⋯,Sm​，则S的元素个数可以通过找出它的每部分元素的个数来确定，即 ∣ S ∣ = ∣ S 1 ∣ + ∣ S 2 ∣ + ⋯ + ∣ S m ∣ |S| = |S_{1}| + |S_{2}| + cdots + |S_{m}| ∣S∣=∣S1​∣+∣S2​∣+⋯+∣Sm​∣ 。通俗地说，一件事可以用 m m m类不同的方法完成，其中第 i i i类有 a i a_{i} ai​种不同的方法，则总方法数为 a 1 + a 2 + ⋯ + a m a_{1}+a_{2}+cdots+a_{m} a1​+a2​+⋯+am​ 。加法原理是全体等于部分和的公式化描述。在加法原理中，如果集合 S 1 , S 2 , ⋯   , S m S_{1},S_{2},cdots,S_{m} S1​,S2​,⋯,Sm​可以重叠，就是容斥原理。
(2) 乘法原理：令S是元素的序偶 ( a , b ) (a, b) (a,b)的集合，其中第 1 1 1个元素 a a a来自大小为 p p p的一个集合，而对于 a a a的每个选择，元素 b b b有 q q q种选择，则 S S S的大小为 p × q p×q p×q。乘法原理是加法原理的推论，因为整数的乘法就是重复的加法。例如，从8男7女5儿童中选出一男一女一儿童的方法有 8 × 7 × 5 = 280 8×7×5 = 280 8×7×5=280种。

2. 排列

排列是有序的，把 n n n个元素的集合 S S S的一个 r r r排列理解为 n n n个元素中的 r r r个元素的有序摆放。
(1) 不可重复排列数 ：从 n n n个不同的物品中不重复地取出 r r r个，排列数 P n r = n ( n − 1 ) ( n − 2 ) ⋯ ( n − r + 1 ) = n ! ( n − r ) ! P_{n}^{r}=n(n – 1)(n – 2)cdots(n – r + 1)=frac{n!}{(n – r)!} Pnr​=n(n−1)(n−2)⋯(n−r+1)=(n−r)!n!​ 。
(2) 可重复排列数：从 n n n个不同的物品中可重复地取出 r r r个，排列数为 n r n^{r} nr。
例如，对26个字母排序，要求5个元音字母中的任意两个不能连续出现，问有多少种排序方法？
首先21个辅音字母排序，有 21 ! ( 21 − 21 ) ! = 21 ! frac{21!}{(21 – 21)!}=21! (21−21)!21!​=21!种 ( 0 ! = 1 ) (0!=1) (0!=1)，然后把元音字母插到这21个辅音字母之间，有22个位置可以插，等价于从22个物品中选出5个，有 22 ! ( 22 − 5 ) ! = 22 ! 17 ! frac{22!}{(22 – 5)!}=frac{22!}{17!} (22−5)!22!​=17!22!​种方法；最后根据乘法原理，两个步骤相乘，得出有 21 ! × 22 ! 17 ! 21!×frac{22!}{17!} 21!×17!22!​种方法。
上面的排列是线性的，所有元素排成一条线。如果不是排成一条线，而是一个圆，由于产生了循环，那么排列的数量要减少。如果把这个圆排列拆成线性排列，可以从任意位置拆开。
(3) 圆排列（循环排列，环排列）的排列数：从 n n n个元素中选 r r r个的圆排列的排列数为 P n r r = n ! r ( n − r ) ! frac{P_{n}^{r}}{r}=frac{n!}{r(n – r)!} rPnr​​=r(n−r)!n!​ 。

3.组合

排列是有序的，组合是无序的，把 n n n个元素的集合 S S S的 r r r组合理解为从 S S S的 n n n个元素中 对 r r r个元素的无序选择，即 r r r是 S S S的一个子集。 如果 S S S中的元素都不相同，组合数 C n r = ( n r ) = P n r r ! = n ! r ! ( n − r ) ! C_{n}^{r}=inom{n}{r}=frac{P_{n}^{r}}{r!}=frac{n!}{r!(n – r)!} Cnr​=(rn​)=r!Pnr​​=r!(n−r)!n!​ ，注意这里的符号，组合数的表示有两种常用符号： C n r C_{n}^{r} Cnr​、 ( n r ) inom{n}{r} (rn​)，其中 C n r C_{n}^{r} Cnr​的 n n n在下面， ( n r ) inom{n}{r} (rn​)的 n n n在上面。

例如，平面上的20个点，没有3个点共线。问这些点能确定多少条直线？能确定多少个三角形？

任意两点确定一条直线，即 n = 20 n = 20 n=20， r = 2 r = 2 r=2， C n r = ( n r ) = 20 ! 2 ! ( 20 − 2 ) ! = 190 C_{n}^{r}=inom{n}{r}=frac{20!}{2!(20 – 2)!}=190 Cnr​=(rn​)=2!(20−2)!20!​=190；任意3点确定一个三角形， C n r = ( 20 3 ) = 20 ! 3 ! ( 20 − 3 ) ! = 1140 C_{n}^{r}=inom{20}{3}=frac{20!}{3!(20 – 3)!}=1140 Cnr​=(320​)=3!(20−3)!20!​=1140 。

组合数有3个重要性质。

(1) C n r = C n n − r C_{n}^{r}=C_{n}^{n – r} Cnr​=Cnn−r​ 。从 n n n个元素中拿出 r r r个，等价于从 n n n个元素中丢掉 n − r n – r n−r个。

(2) C n r = C n − 1 r + C n − 1 r − 1 C_{n}^{r}=C_{n – 1}^{r}+C_{n – 1}^{r – 1} Cnr​=Cn−1r​+Cn−1r−1​ ，称为帕斯卡公式。可以用DP思路证明，取或不取第 n n n个元素：若取第 n n n个元素，则在剩下的 n − 1 n – 1 n−1个元素中选 r − 1 r – 1 r−1个；若不取第 n n n个元素，则在剩下的 n − 1 n – 1 n−1个元素中选 r r r个。这个性质很有用，需要计算 C n r C_{n}^{r} Cnr​时，为避免阶乘计算，可利用这个递推关系。这个性质也用于构造帕斯卡三角（杨辉三角）。

(3) C n 0 + C n 1 + C n 2 + ⋯ + C n n = 2 n C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+cdots +C_{n}^{n}=2^{n} Cn0​+Cn1​+Cn2​+⋯+Cnn​=2n 。这个表达式体现了组合数与二进制的关系，竞赛时常常用到。一个 n n n位的二进制数，其数值范围为 0 ～ 2 n − 1 0～2^{n}-1 0～2n−1，共有 2 n 2^{n} 2n个，每个二进制数就是一种组合。例如， n = 4 n = 4 n=4， r = 2 r = 2 r=2 ，有 C 4 2 = 6 C_{4}^{2}=6 C42​=6种组合，对应二进制数：0011、0101、0110、1001、1010、1100。

计算 C n r C_{n}^{r} Cnr​的方法有多种，见第3节“二项式定理和杨辉三角”。

4. 多重集的排列和组合

如果 S S S中的元素可以相同，称为多重集，如 S = { 5 × a , 7 × b , 4 × c } S = {5×a, 7×b, 4×c} S={
5×a,7×b,4×c} 。下面给出多重集的排列和组合的定义。

(1) 无限多重集的排列：令 S S S是一个多重集，它有 k k k个不同的元素，每个元素都有无穷重复个数，那么 S S S的 r r r排列的个数为 k r k^{r} kr 。

(2) 有限多重集的排列：令 S S S是一个多重集，它有 k k k个不同的元素，每个元素的重数分别为 n 1 , n 2 , ⋯   , n k n_{1},n_{2},cdots,n_{k} n1​,n2​,⋯,nk​ ， S S S的大小为 n = n 1 + n 2 + ⋯ + n k n = n_{1}+n_{2}+cdots +n_{k} n=n1​+n2​+⋯+nk​ ，则 S S S的 n n n排列的个数为 n ! n 1 ! n 2 ! ⋯ n k ! frac{n!}{n_{1}!n_{2}!cdots n_{k}!} n1​!n2​!⋯nk​!n!​ 。

(3) 有限多重集的组合：令 S S S是一个多重集，它有 k k k个不同的元素，每个元素都有无穷重复个数，那么 S S S的 r r r组合的个数为 C r + k − 1 r = ( r + k − 1 r ) = C r + k − 1 k − 1 = ( r + k − 1 k − 1 ) C_{r + k – 1}^{r}=inom{r + k – 1}{r}=C_{r + k – 1}^{k – 1}=inom{r + k – 1}{k – 1} Cr+k−1r​=(rr+k−1​)=Cr+k−1k−1​=(k−1r+k−1​) 。

【习题】 洛谷P2822/P5520/P3197/P2290/P4931/P5596。

2 鸽巢原理

鸽巢原理（Pigeonhole Principle），也称为抽屉原理（Drawer Principle），是很基本的组合原理。鸽巢原理的生活原型是 n + 1 n + 1 n+1只鸽子住在 n n n个巢里，那么至少有一个巢里有两只或更多鸽子。稍微推广一下， k × n + 1 k×n + 1 k×n+1只鸽子住在 n n n个巢里，那么至少有一个巢里有 k + 1 k + 1 k+1只或更多鸽子。
有简单形式和加强形式的鸽巢原理。另外，鸽巢原理是Ramsey定理的一个特例。

1. 鸽巢原理的简单形式

鸽巢原理的简单形式：把 n + 1 n + 1 n+1个物体放进 n n n个盒子，至少有一个盒子包含两个或更多的物体。
鸽巢原理的题目可以用“抽屉法”或“隔板法”来思考。竞赛题常常与整数求余结合，把余数用抽屉来处理。下面给出一些例子。
(1) 370人中，至少有两人的生日相同。
题解：把365天分成365个抽屉，那么把365人放进365个抽屉后，剩下的人不管放进哪个抽屉，里面都已经有人了。
(2) n n n个人，认识的人互相握手，至少有两个人握手次数相同。
题解：每人跟其他人握手，最少可以是0次，最多可以是 n − 1 n – 1 n−1次。
如果握手最少的张三握手0次，那么剩下的 n − 1 n – 1 n−1人中，握手最多的人不会超过 n − 2 n – 2 n−2次。 0 ～ n − 2 0～n – 2 0～n−2共有 n − 1 n – 1 n−1种情况。
如果握手最少的张三握手1次，那么剩下的 n − 1 n – 1 n−1人中，握手最多的李四除了跟张三握手一次，跟其他 n − 2 n – 2 n−2人最多握手 n − 2 n – 2 n−2次，李四最多握手 n − 1 n – 1 n−1次。 1 ～ n − 1 1～n – 1 1～n−1，共有 n − 1 n – 1 n−1种情况。
如果握手最少的张三握手两次，那么剩下的 n − 1 n – 1 n−1人中，握手最多的李四除了跟张三握手一次，跟其他 n − 2 n – 2 n−2人最多握手 n − 2 n – 2 n−2次，李四最多握手 n − 1 n – 1 n−1次。 2 ～ n − 1 2～n – 1 2～n−1，共有 n − 2 n – 2 n−2种情况。
……
所以，握手次数最多有 n − 1 n – 1 n−1种情况，最少只有一种情况。把最多的 n − 1 n – 1 n−1种情况看成 n − 1 n – 1 n−1个抽屉， n n n个人放进这 n − 1 n – 1 n−1个抽屉，至少有一个抽屉里面有两人。
(3) 有 K K K种糖果，给出每种糖果的数量；要求不能连续两次吃同样的糖果，问有没有可行的吃糖方案。
题解：找出最多的一种糖果，把它的数量 N N N看作 N N N个隔板（或抽屉），隔成 N N N个空间（把每个隔板的右边看成一个空间）；其他所有糖果的数量为 S S S。
若 S < N − 1 S < N – 1 S<N−1，把 s s s个糖果放到隔板之间，这 N N N个隔板不够放，必然至少有两个隔板之间没有糖果，由于这两个隔板是同一种糖果，所以无解。
若 S ≥ N − 1 S≥N – 1 S≥N−1时，肯定有解。其中一个解是：把 S S S个糖果按顺序排成一个长队，其中同种类的糖果放在一起，然后每次取 N N N个糖果，按顺序一个一个地放进 N N N个空间。由于隔板数量比每种糖果的数量都多，所以不可能有两个同样的糖果被放进一个空间里。把 s s s个糖果放完，就是一个解，一些隔板里面可能放好几种糖果。
(4) 任意5个自然数，其中必有3个数的和能被3整除。
题解：任何数除以3，余数可以是0、1、2。造3个抽屉，分别表示3种余数的情况。把5个数按余数放进3个抽屉。
若5个数分布在3个抽屉里，那么从3个抽屉中各取一个，其和能被3整除。
若5个数只分布在两个抽屉里，那么至少有一个抽屉里有3个数，取出这3个数，其和能被3整除。
若5个数全部在一个抽屉里，任取3个数，其和肯定被3整除。
(5) 任意7个不同的自然数，其中必有两个整数的和或差是10的倍数。
题解：这些数除以10，余数为0 – 9，造10个抽屉分别表示10种余数的情况。然后，把6、7、8、9这4个抽屉分别与4、3、2、1这4个抽屉合并，保持原来的0、5抽屉不变，得到新的6个抽屉。那么，至少有一个抽屉里面有两个数，它们的和或差是10的倍数。
(6) poj 2356。

例1 Find a multiple(poj 2356)
问题描述：输入 n n n个正整数， n ≤ 10000 n≤10000 n≤10000。每个数都不大于 15000 15000 15000，可能相同。从中找出一些数，使它们的和是 n n n的倍数。
输入：第 1 1 1行输入整数 n n n；后面 n n n行中，每行输入一个整数。
输出：如果无解，输出 0 0 0。如果有解，第1行打印数字的数量，后面每行打印出一个数字，顺序任意。如果有多个解，随便打印一个解。
先求出这 n n n个数的前缀和 s u m [ 1 ] , s u m [ 2 ] , ⋯   , s u m [ n ] sum[1],sum[2],cdots,sum[n] sum[1],sum[2],⋯,sum[n]，如果其中有 n n n的倍数，直接输出。
如果这 n n n个前缀和都不是 n n n的倍数，把这些前缀和对 n n n求余，余数为 1 ～ n − 1 1～n – 1 1～n−1，共 n − 1 n – 1 n−1个，用 n − 1 n – 1 n−1个抽屉表示这 n − 1 n – 1 n−1个余数。把 n n n个前缀和放进这 n − 1 n – 1 n−1个抽屉，必然有一个抽屉中有两个前缀和。这两个前缀和相减，得到一个区间，就是答案。
poj 3370是一道类似的题目。

2. 鸽巢原理的加强形式

鸽巢原理的简单形式是加强形式的特例。
鸽巢原理的加强形式：令 q 1 , q 2 , ⋯   , q n q_{1},q_{2},cdots,q_{n} q1​,q2​,⋯,qn​为正整数，如果将 q 1 + q 2 + ⋯ + q n − n + 1 q_{1}+q_{2}+cdots+q_{n}-n + 1 q1​+q2​+⋯+qn​−n+1个物体放入 n n n个盒子，那么，或者第1个盒子至少含有 q 1 q_{1} q1​个物体，或者第2个盒子至少含有 q 2 q_{2} q2​个物体，……或者第 n n n个盒子至少含有 q n q_{n} qn​个物体。
例如，一个篮子里面有苹果、香蕉、梨，保证篮子里或者至少有8个苹果，或者至少有6个香蕉，或者至少有9个梨。问放进篮子的最少水果数量是多少？
题解：根据加强形式，无论如何选择， 8 + 6 + 9 − 3 + 1 = 21 8 + 6 + 9 – 3 + 1 = 21 8+6+9−3+1=21个水果满足要求。

3. Ramsey定理

鸽巢原理是Ramsey定理的一个特例，Ramsey定理是鸽巢原理的扩展。Ramsey定理在竞赛中很少见，这里简要介绍。

Ramsey定理的一个简单例子是：在6人（或更多人）中，或者有3人，每两人都互相认识；或者有3人，每两人都不认识。

证明 :

用6个点 A A A、 B B B、 C C C、 D D D、 E E E、 F F F代表6个人。如果两人认识，连一条红线，否则连一条蓝线。从 A A A点出发的5条线 A B AB AB、 A C AC AC、 A D AD AD、 A E AE AE、 A F AF AF，它们的颜色不超过两种。根据抽屉原理，其中至少有3条线同色，不妨设 A B AB AB、 A C AC AC、 A D AD AD同为红色。下面看 B B B、 C C C、 D D D这3个点，如果 B C BC BC、 B D BD BD、$CD 3 条线中有一条（不妨设为 3条线中有一条（不妨设为 3条线中有一条（不妨设为BC ）为红色，那么 ）为红色，那么 ）为红色，那么A 、 、 、B 、 、 、C 互相用红线相连，这 3 人互相认识；如果 互相用红线相连，这3人互相认识；如果 互相用红线相连，这3人互相认识；如果BC 、 、 、BD 、 、 、CD 3 条线全为蓝色，那么 3条线全为蓝色，那么 3条线全为蓝色，那么B 、 、 、C 、 、 、D$这3个人互相不认识。

3. 二项式定理和杨辉三角

1. 杨辉三角计算公式

组合公式 C n r = ( n r ) = n ! r ! ( n − r ) ! C_{n}^{r}=inom{n}{r}=frac{n!}{r!(n – r)!} Cnr​=(rn​)=r!(n−r)!n!​，把 C n r C_{n}^{r} Cnr​作为二项式系数。
杨辉三角（国外称帕斯卡三角）是二项式系数的典型应用。杨辉三角是排列成如下形式三角形的数字：

​ 1

​ 1 1

​ 1 2 1

​ 1 3 3 1

​ 1 4 6 4 1

1 5 10 10 5 1

杨辉三角中的每个数是它“肩上”两个数的和。如果编程求杨辉三角第 n n n行的数字，可以模拟这个推导过程，逐层累加，复杂度为 O ( n 2 ) O(n^{2}) O(n2)。如果改用数学公式计算，能直接得到结果，这个公式是 ( 1 + x ) n (1 + x)^{n} (1+x)n。
观察 ( 1 + x ) n (1 + x)^{n} (1+x)n的展开：
( 1 + x ) 0 = 1 (1 + x)^{0}=1 (1+x)0=1
( 1 + x ) 1 = 1 + x (1 + x)^{1}=1 + x (1+x)1=1+x
( 1 + x ) 2 = 1 + 2 x + x 2 (1 + x)^{2}=1 + 2x + x^{2} (1+x)2=1+2x+x2
( 1 + x ) 3 = 1 + 3 x + 3 x 2 + x 3 (1 + x)^{3}=1 + 3x + 3x^{2}+ x^{3} (1+x)3=1+3x+3×2+x3
每行展开的系数正好对应杨辉三角每行的数字，所以杨辉三角可以用 ( 1 + x ) n (1 + x)^{n} (1+x)n定义和计算。
如何计算 ( 1 + x ) n (1 + x)^{n} (1+x)n？需要逐一展开算系数吗？并不需要，二项式系数 C n r = ( n r ) = n ! r ! ( n − r ) ! C_{n}^{r}=inom{n}{r}=frac{n!}{r!(n – r)!} Cnr​=(rn​)=r!(n−r)!n!​就是 ( 1 + x ) n (1 + x)^{n} (1+x)n展开后第 r r r项的系数。它们的关系可以这样理解： ( 1 + x ) n (1 + x)^{n} (1+x)n的第 r r r项实际上就是从 n n n个 x x x中选出 r r r个，这就是组合数的定义。所以有
( 1 + x ) n = ∑ r = 0 n C n r x r (1 + x)^{n}=sum_{r = 0}^{n}C_{n}^{r}x^{r} (1+x)n=∑r=0n​Cnr​xr
推导得
( a + b ) n = ∑ r = 0 n C n r a r b n − r = ∑ r = 0 n C n r b r a n − r (a + b)^{n}=sum_{r = 0}^{n}C_{n}^{r}a^{r}b^{n – r}=sum_{r = 0}^{n}C_{n}^{r}b^{r}a^{n – r} (a+b)n=∑r=0n​Cnr​arbn−r=∑r=0n​Cnr​bran−r
这个公式称为二项式定理，可以用数学归纳法证明它。
有了这个公式，求杨辉三角第 n n n行的数字时，就可以用公式直接计算了。不过，二项式系数的计算公式中有 n ! n! n!，如果直接计算 n ! n! n!，数值太大。而且，由于二项式系数增长极快，不管如何计算，大一点的二项式系数都会溢出。所以，题目一般会对输出取模。
当 n n n较大，且需要取模时，二项式系数有两种计算方法。
(1) 利用递推公式： C n r = C n − 1 r + C n − 1 r − 1 C_{n}^{r}=C_{n – 1}^{r}+C_{n – 1}^{r – 1} Cnr​=Cn−1r​+Cn−1r−1​。
这个递推公式就是杨辉三角的定义，即每个数是它“肩上”两个数的和，在7.1节用DP思路给出了证明。利用这个递推公式能避免计算阶乘。递归公式的计算复杂度为 O ( n 2 ) O(n^{2}) O(n2)。
(2) 用逆直接计算。
因为输出取模，那么不用通项公式，直接用公式 C n r = ( n r ) = n ! r ! ( n − r ) ! C_{n}^{r}=inom{n}{r}=frac{n!}{r!(n – r)!} Cnr​=(rn​)=r!(n−r)!n!​计算更快。不过，由于除法不能直接取模，需要用到逆。6.9.3节中提到除法取模用逆来实现 ( a / b )   m o d   m = ( a b − 1 )   m o d   m (a/b)mod m=(ab^{-1})mod m (a/b)modm=(ab−1)modm。用逆计算二项式系数，有
C n r   m o d   m = n ! r ! ( n − r ) !   m o d   m = ( n !   m o d   m ) ( ( r ! ) − 1   m o d   m ) ( ( ( n − r ) ! ) − 1   m o d   m )   m o d   m egin{aligned} &C_{n}^{r}mod m=frac{n!}{r!(n – r)!}mod m \ &=(n!mod m)((r!)^{-1}mod m)(((n – r)!)^{-1}mod m)mod m end{aligned} ​Cnr​modm=r!(n−r)!n!​modm=(n!modm)((r!)−1modm)(((n−r)!)−1modm)modm​
用逆计算二项式系数比递推式更好，效率非常高，从后面的代码得知复杂度为 O ( n ) O(n) O(n)。两种实现见下面例题的代码。

2. 例题

计算杨辉三角
用递推公式计算二项式系数。
例2 计算杨辉三角
问题描述：输出杨辉三角的前 n n n行。
输入：一个整数 n n n， n ≤ 20 n≤20 n≤20。
输出：杨辉三角。
因为没有取模，只能用递推公式计算较小的二项式系数。代码如下。

#include<bits/stdc++.h>
using namespace std;
int a[21][21];
int main(){
            
    int n;cin>>n;
    for(int i = 1;i <= n;i++) a[i][1]=a[i][i]=1;
    for(int i = 1;i <= n;i++)
        for(int j = 2;j < i;j++)
            a[i][j]=a[i-1][j]+a[i-1][j-1]
        for(int i = 1;i <= n;i++){
            
            for(int j = 1;j <= i;j++)
                cout<<a[i][j]<<" ";
            cout<<endl;
        }
    return 0;
}

计算系数
用两种方法计算二项式系数：递推公式、逆。
例3 计算系数（洛谷P1313）
问题描述：给定一个多项式 ( a x + b y ) k (ax + by)^{k} (ax+by)k，求出多项式展开后第 x n × y m x^{n}×y^{m} xn×ym项的系数。
输入：输入5个整数，分别是 a a a、 b b b、 k k k、 n n n、 m m m，用空格隔开。
输出：输出一个整数，表示所求的系数。系数可能很大，对10007取模。
数据范围： 0 ≤ k ≤ 1000 0≤k≤1000 0≤k≤1000， 0 ≤ n 0≤n 0≤n， m ≤ k m≤k m≤k， n + m = k n + m = k n+m=k， 0 ≤ a 0≤a 0≤a， b ≤ 1 0 9 b≤10^{9} b≤109。
根据二项式定理，有
( a x + b y ) k = ∑ r = 1 k C k r ( a x ) r ( b y ) k − r = ∑ r = 1 k C k r a r x r b k − r y k − r = ∑ r = 1 k ( C k r a r b k − r ) x r y k − r (ax + by)^{k}=sum_{r = 1}^{k}C_{k}^{r}(ax)^{r}(by)^{k – r}=sum_{r = 1}^{k}C_{k}^{r}a^{r}x^{r}b^{k – r}y^{k – r}=sum_{r = 1}^{k}(C_{k}^{r}a^{r}b^{k – r})x^{r}y^{k – r} (ax+by)k=∑r=1k​Ckr​(ax)r(by)k−r=∑r=1k​Ckr​arxrbk−ryk−r=∑r=1k​(Ckr​arbk−r)xryk−r
本题需要计算快速幂和二项式系数。
下面给出两种计算二项式系数的方法：一种用递推公式求二项式系数，请读者对比例7.2的递推写法；另一种是用逆直接计算二项式公式。
(1) 用递推公式计算二项式系数（DFS写法）。

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
#define mod 10007
int c[N][N]; //存二项式系数
int fastPow(int a,int n){
             //标准快速幂
    int ans = 1;
    a %= mod; //防止下面的ans*a越界
    while(n){
            
        if(n&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        n >>= 1;
    }
    return ans;
}
int dfs(int n,int m){
             
    if(!m) return c[n][m] = 1; //用递推公式求二项式系数，原代码此处有误，应为1
    if(m == 1)return c[n][m]=n;
    if(c[n][m])return c[n][m];//记忆化
    if(n - m < m)m = n - m;
    return c[n][m]=(dfs(n - 1,m)+dfs(n - 1,m - 1))%mod;
}
int main(){
            
    int a,b,k,n,m;cin>>a>>b>>k>>n>>m;
    c[1][0]=c[1][1]=1;
    int ans = 1;
    ans*=(fastPow(a,n)*fastPow(b,m))%mod;
    ans *=dfs(k,n)%mod;
    ans %= mod;
    cout<<ans;
    return 0;
}

(2) 用逆直接计算二项式公式。
对组合数的计算，需要预计算阶乘和逆，复杂度为 O ( n ) O(n) O(n)，再用逆直接计算。总复杂度为 O ( n ) O(n) O(n)。

#include <bits/stdc++.h>
using namespace std;
#define mod 10007
int fac[10001];
int inv[10001];
int fastPow(int a, int n) {
            
    int res = 1;
    a %= mod;
    while (n > 0) {
            
        if (n & 1) {
            
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}
int C(int n, int m) {
            
    return (fac[n] * inv[m] % mod * inv[n - m] % mod) % mod;
}
int main() {
            
    int a, b, n, m, k, ans;
    cin >> a >> b >> k >> n >> m;
    fac[0] = 1;
    for (int i = 1; i <= n + m; i++) {
            
        fac[i] = (fac[i - 1] * i) % mod;
        inv[i] = fastPow(fac[i], mod - 2);
    }
    ans = (fastPow(a, n) % mod * fastPow(b, m) % mod * C(k, n) % mod) % mod;
    cout << ans;
    return 0;
}

4 卢卡斯定理

卢卡斯定理（Lucas Theorem）用于计算组合数取模，即求 C n r   m o d   m C_{n}^{r}mod m Cnr​modm，其中 m m m为素数。

1. 卢卡斯定理和证明

前面提到组合数的计算可以用逆，但是也有局限。回顾逆的定义：给定整数 a a a，满足 g c d ( a , m ) = 1 gcd(a, m)=1 gcd(a,m)=1，称 a x ≡ 1 (   m o d   m ) axequiv1(mod m) ax≡1(modm)的一个解为 a a a模 m m m的逆，记为 a − 1 a^{-1} a−1。从要求 g c d ( a , m ) = 1 gcd(a, m)=1 gcd(a,m)=1可以看出，模 m m m最好是一个大于 a a a的素数，才能保证 g c d ( a , m ) = 1 gcd(a, m)=1 gcd(a,m)=1。但是，7.3节的利用逆计算组合数：
C n r   m o d   m = ( n !   m o d   m ) ( ( r ! ) − 1   m o d   m ) ( ( ( n − r ) ! ) − 1   m o d   m )   m o d   m C_{n}^{r}mod m=(n!mod m)((r!)^{-1}mod m)(((n – r)!)^{-1}mod m)mod m Cnr​modm=(n!modm)((r!)−1modm)(((n−r)!)−1modm)modm
如果模 m m m比 n n n小，就不能保证 n n n和 n − r n – r n−r的逆元存在。此时不能用逆计算，但是如果用递推公式计算，复杂度为 O ( n 2 ) O(n^{2}) O(n2)，比较低效。卢卡斯定理仍能高效率地处理这种情况。

卢卡斯定理对于非负整数 n n n、 r r r和素数 m m m，有
C n r ≡ ∏ i = 0 k C n i r i (   m o d   m ) C_{n}^{r}equivprod_{i = 0}^{k}C_{n_{i}}^{r_{i}}(mod m) Cnr​≡∏i=0k​Cni​ri​​(modm)
或者写成
C n r   m o d   m = ∏ i = 0 k C n i r i   m o d   m C_{n}^{r}mod m=prod_{i = 0}^{k}C_{n_{i}}^{r_{i}}mod m Cnr​modm=∏i=0k​Cni​ri​​modm
其中， n = n k m k + ⋯ + n 1 m + n 0 n = n_{k}m^{k}+cdots + n_{1}m + n_{0} n=nk​mk+⋯+n1​m+n0​和 r = r k m k + ⋯ + r 1 m + r 0 r = r_{k}m^{k}+cdots + r_{1}m + r_{0} r=rk​mk+⋯+r1​m+r0​是 n n n和 r r r的 m m m进制展开，也就是把 n n n和 r r r表示为 m m m进制数，对 m m m进制下的每位分别计算组合数，最后乘起来。例如，计算 C 17 8   m o d   7 C_{17}^{8}mod 7 C178​mod7， 17 = 2 × 7 1 + 3 × 7 0 17 = 2×7^{1}+3×7^{0} 17=2×71+3×70， 8 = 1 × 7 1 + 1 × 7 0 8 = 1×7^{1}+1×7^{0} 8=1×71+1×70， C 17 8   m o d   7 = C 2 1 × C 3 1   m o d   7 = 6   m o d   7 = 6 C_{17}^{8}mod 7 = C_{2}^{1}×C_{3}^{1}mod 7 = 6mod 7 = 6 C178​mod7=C21​×C31​mod7=6mod7=6。 注意，在这个公式中有可能 n i < r i n_{i}<r_{i} ni​<ri​，此时规定 C n i r i = 0 C_{n_{i}}^{r_{i}} = 0 Cni​ri​​=0。如果有一个 n i < r i n_{i}<r_{i} ni​<ri​，就有 C n r   m o d   m = 0 C_{n}^{r}mod m = 0 Cnr​modm=0。

编程时用卢卡斯定理的另一种表达：
C n r ≡ C n   m o d   m r   m o d   m ⋅ C n / m r / m (   m o d   m ) C_{n}^{r}equiv C_{nmod m}^{rmod m}cdot C_{n/m}^{r/m}(mod m) Cnr​≡Cnmodmrmodm​⋅Cn/mr/m​(modm)

下面证明这个公式。
证明对于素数 m m m， r ∈ ( 0 , m ) rin(0, m) r∈(0,m)，有
C m r = m ! r ! ( m − r ) ! = ( m − 1 ) ! ( r − 1 ) ! ( m − r ) ! × m r = C m − 1 r − 1 × m r ≡ 0 (   m o d   m ) C_{m}^{r}=frac{m!}{r!(m – r)!}=frac{(m – 1)!}{(r – 1)!(m – r)!}×frac{m}{r}=C_{m – 1}^{r – 1}×frac{m}{r}equiv0(mod m) Cmr​=r!(m−r)!m!​=(r−1)!(m−r)!(m−1)!​×rm​=Cm−1r−1​×rm​≡0(modm)

将其代入二项式定理的展开式，得
( 1 + x ) m = ∑ r = 0 m C m r × x r = 1 + ∑ r = 1 m − 1 C m r × x r + x m ≡ 1 + x m (   m o d   m ) (1 + x)^{m}=sum_{r = 0}^{m}C_{m}^{r}×x^{r}=1+sum_{r = 1}^{m – 1}C_{m}^{r}×x^{r}+x^{m}equiv1 + x^{m}(mod m) (1+x)m=∑r=0m​Cmr​×xr=1+∑r=1m−1​Cmr​×xr+xm≡1+xm(modm)
下面推导卢卡斯定理。令 n = s m + a n = sm + a n=sm+a，有
( 1 + x ) n = ( 1 + x ) s m + a = ( 1 + x ) s m ( 1 + x ) a ≡ ( 1 + x m ) s ( 1 + x ) a ≡ ( ∑ i = 0 s C s i × x i m ) × ( ∑ j = 0 a C a j × x j ) (   m o d   m ) egin{aligned} (1 + x)^{n}&=(1 + x)^{sm + a}=(1 + x)^{sm}(1 + x)^{a}equiv(1 + x^{m})^{s}(1 + x)^{a}\ &equiv(sum_{i = 0}^{s}C_{s}^{i}×x^{im}) imes(sum_{j = 0}^{a}C_{a}^{j}×x^{j})(mod m) end{aligned} (1+x)n​=(1+x)sm+a=(1+x)sm(1+x)a≡(1+xm)s(1+x)a≡(i=0∑s​Csi​×xim)×(j=0∑a​Caj​×xj)(modm)​
又根据二项式定理 ( 1 + x ) n = ∑ r = 0 n C n r × x r (1 + x)^{n}=sum_{r = 0}^{n}C_{n}^{r}×x^{r} (1+x)n=∑r=0n​Cnr​×xr，与上式对比得
∑ r = 0 n C n r × x r ≡ ( ∑ i = 0 s C s i × x i m ) × ( ∑ j = 0 a C a j × x j ) (   m o d   m ) sum_{r = 0}^{n}C_{n}^{r}×x^{r}equiv(sum_{i = 0}^{s}C_{s}^{i}×x^{im}) imes(sum_{j = 0}^{a}C_{a}^{j}×x^{j})(mod m) ∑r=0n​Cnr​×xr≡(∑i=0s​Csi​×xim)×(∑j=0a​Caj​×xj)(modm)

对比两边第 x r x^{r} xr次项的系数，根据 r = i m + j r = im + j r=im+j， i = r / m i = r/m i=r/m， j = r   m o d   m j = rmod m j=rmodm， a = n   m o d   m a = nmod m a=nmodm， s = n / m s = n/m s=n/m，得
C n r ≡ C s i × C a j (   m o d   m ) ≡ C n / m r / m × C n   m o d   m r   m o d   m (   m o d   m ) C_{n}^{r}equiv C_{s}^{i}×C_{a}^{j}(mod m)equiv C_{n/m}^{r/m}×C_{nmod m}^{rmod m}(mod m) Cnr​≡Csi​×Caj​(modm)≡Cn/mr/m​×Cnmodmrmodm​(modm)
注意，公式分为两部分：
(1) C n   m o d   m r   m o d   m (   m o d   m ) C_{nmod m}^{rmod m}(mod m) Cnmodmrmodm​(modm)，因为 r   m o d   m rmod m rmodm和 n   m o d   m nmod m nmodm都比 m m m小，仍然可以使用“用逆直接计算二项式公式”来求解；
(2) C n / m r / m C_{n/m}^{r/m} Cn/mr/m​，继续用卢卡斯定理展开，用递归实现。

2. 模板题

下面给出一道卢卡斯定理的模板题，实现了上述公式的两部分计算。
例5 卢卡斯定理（洛谷P3807）
问题描述：给定整数 a a a、 b b b、 m m m，求 C a + b a   m o d   m C_{a + b}^{a}mod m Ca+ba​modm。保证 m m m为素数。
输入：第1行输入一个整数 T T T，表示测试数量；后面 T T T行中，每行输入3个整数 a a a、 b b b、 m m m。
输出：共 T T T行，每行输出一个整数，表示答案。
数据范围： 0 ≤ a 0leq a 0≤a， b b b， m ≤ 100000 mleq100000 m≤100000， 1 ≤ T ≤ 10 1leq Tleq10 1≤T≤10。
下面代码的复杂度如何？Lucas()函数用递归实现辗转相除 n   m o d   m nmod m nmodm，当 m o d mod mod是一个较大的素数时，Lucas()函数只需递归很少次。计算主要花在预计算阶乘上，复杂度为 O ( n ) O(n) O(n)。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
ll fac[N]; 
ll fastPow(ll a,ll n,ll m){
             //预计算阶乘，取模 //标准快速幂
    a %= m; 
    ll ans = 1; 
    while(n){
            
        if(n&1) ans=(ans*a)%m;
        a=(a*a)%m;
        n >>= 1;
    }
    return ans;
}
ll inverse(ll a, int m){
             return fastPow(a,m - 2,m);}//用费马小定理计算逆
ll C(ll n,ll r,int m){
             //用逆计算C(n mod m,r mod m)mod m
    if(r>n)return 0;
    return (fac[n]*inverse(r,m))%m*inverse(n - r,m)%m;
}
ll Lucas(ll n,ll r,int m){
             
    if(r == 0) return 1; //用递归计算C(n,r)mod m
    return C(n%m,r%m,m)*Lucas(n/m,r/m,m)%m; //分两部分计算
}
int main(){
             
    int T;cin>>T;
    while(T--){
            
        int a,b,m; cin>>a>>b>>m;
        fac[0]=1;
        for(int i = 1;i <= m;i++)fac[i]=(fac[i - 1]*i)%m; //预计算阶乘，取模
        cout<<Lucas(a + b,a,m)<<endl;
    }
    return 0;
}

3. 例题

例6 Binomial coefficients(poj 3219)
问题描述：判断组合数 C n r C_{n}^{r} Cnr​的奇偶。
输入：输入两个整数 n n n和 r r r。 0 ≤ k ≤ n ≤ 2 31 0leq kleq nleq2^{31} 0≤k≤n≤231。
输出：如果 C n r C_{n}^{r} Cnr​是偶数，则输出0，否则输出1。
将题目转换为对2取模，计算 C n r   m o d   2 C_{n}^{r}mod 2 Cnr​mod2，若等于0则是偶数，若等于1则是奇数。可以用卢卡斯定理计算 C n r   m o d   2 C_{n}^{r}mod 2 Cnr​mod2的值。不过，更简单的做法是根据卢卡斯定理直接推导出结果。
根据卢卡斯定理 C n r   m o d   m = ∏ i = 0 k C n i r i   m o d   m C_{n}^{r}mod m=prod_{i = 0}^{k}C_{n_{i}}^{r_{i}}mod m Cnr​modm=∏i=0k​Cni​ri​​modm，当 m = 2 m = 2 m=2时， C n r   m o d   2 = ∏ i = 0 k C n i r i   m o d   2 C_{n}^{r}mod 2=prod_{i = 0}^{k}C_{n_{i}}^{r_{i}}mod 2 Cnr​mod2=∏i=0k​Cni​ri​​mod2，其中 n = n k × 2 k + ⋯ + n 1 × 2 + n 0 n = n_{k}×2^{k}+cdots + n_{1}×2 + n_{0} n=nk​×2k+⋯+n1​×2+n0​， r = r k × 2 k + ⋯ + r 1 × 2 + r 0 r = r_{k}×2^{k}+cdots + r_{1}×2 + r_{0} r=rk​×2k+⋯+r1​×2+r0​，是 n n n和 r r r的二进制展开。 前面提到，如果 n i < r i n_{i}<r_{i} ni​<ri​，规定 C n i r i = 0 C_{n_{i}}^{r_{i}} = 0 Cni​ri​​=0，如果有一个 n i < r i n_{i}<r_{i} ni​<ri​，就有 C n r   m o d   m = 0 C_{n}^{r}mod m = 0 Cnr​modm=0。所以得出以下结论。
(1)将 n n n和 r r r的二进制作与运算，如果有 n & r = r n&r = r n&r=r，那么 ∏ i = 0 k C n i r i prod_{i = 0}^{k}C_{n_{i}}^{r_{i}} ∏i=0k​Cni​ri​​的每一位或者是 C 1 1 C_{1}^{1} C11​，或者是 C 0 0 C_{0}^{0} C00​，都等于1。答案为奇数。
(2)如果 n & r ≠ r n&r≠r n&r=r，必然有一个 C n i r i = 0 C_{n_{i}}^{r_{i}} = 0 Cni​ri​​=0。答案为偶数。

【习题】
洛谷P1680/P3726/P2480/P4345/P2675。
提示：卢卡斯定理中的模 m m m是一个素数，如果 m m m不是素数，可以用“扩展卢卡斯定理”，请通过洛谷P4720“扩展卢卡斯定理”了解。

5 容斥原理

容斥原理（Inclusion – Exclusion Principle）是一个基本的计数原理：不能重复也不能遗漏。在计数时，有时情况比较多，相互有重叠。为了使重叠部分不被重复计算，可以这样处理：先不考虑重叠的情况，把所有对象的数目先计算出来，然后再减去重复计算的数目。这种计数方法称为容斥原理。

1. 容斥原理的简单形式

容斥原理的简单形式：设 A A A和 B B B是分别具有性质 P 1 P_{1} P1​和 P 2 P_{2} P2​的有限集，则有
∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∩ B ∣ |A cup B| = |A| + |B| – |A cap B| ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

例1：10个学生选修古代诗歌，6个学生选修现代诗歌，3个学生同时选修古代诗歌和现代诗歌。问共有多少学生选修诗歌？
解：用集合 A A A表示学古代诗歌的学生， B B B表示学现代诗歌的学生。学诗歌的学生数量为 ∣ A ∪ B ∣ |A cup B| ∣A∪B∣，同时学两门诗歌的学生数量为 ∣ A ∩ B ∣ |A cap B| ∣A∩B∣。学诗歌的总人数为 ∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∩ B ∣ = 10 + 6 − 3 = 13 |A cup B| = |A| + |B| – |A cap B| = 10 + 6 – 3 = 13 ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣=10+6−3=13。

例2：一根长60m的绳子，每隔3m做一个记号，每隔4m也做一个记号，然后把有记号的地方剪断。问绳子共被剪成了多少段？
解：3的倍数有20个，不算绳子两头，有 20 − 1 = 19 20 – 1 = 19 20−1=19个记号；4的倍数有15个；既是3的倍数又是4的倍数有 60 ÷ ( 3 × 4 ) = 5 60div(3×4)=5 60÷(3×4)=5个。所以，记号的总数为 ( 20 − 1 ) + ( 15 − 1 ) − ( 5 − 1 ) = 29 (20 – 1)+(15 – 1)-(5 – 1)=29 (20−1)+(15−1)−(5−1)=29，绳子被剪成29段。

2. 容斥原理的定义

容斥原理 (1) 集合 S S S的子集 A 1 A_{1} A1​有性质 P 1 P_{1} P1​， A 2 A_{2} A2​有性质 P 2 P_{2} P2​， ⋯ cdots ⋯， A n A_{n} An​有性质 P n P_{n} Pn​，有以下两种定义。
(1)集合 S S S中不具有性质 P 1 P_{1} P1​， P 2 P_{2} P2​， ⋯ cdots ⋯， P n P_{n} Pn​的对象个数为
∣ A 1 ‾ ∩ A 2 ‾ ∩ ⋯ ∩ A n ‾ ∣ = ∣ S ∣ − ∑ ∣ A i ∣ + ∑ ∣ A i ∩ A j ∣ − ∑ ∣ A i ∩ A j ∩ A k ∣ + ⋯ + ( − 1 ) n ∣ A 1 ‾ ∩ A 2 ‾ ∩ ⋯ ∩ A n ‾ ∣ egin{array} {r}{|overline {A_{1}}cap overline {A_{2}} cap cdots cap overline {A_{n}}| = |S|-sum |A_{i}|+sum |A_{i}cap A_{j}|-}\ {sum |A_{i}cap A_{j}cap A_{k}|+cdots +(-1)^{n}| overline {A_{1}}cap overline {A_{2}}cap cdots cap overline {A_{n}}| }end{array} ∣A1​​∩A2​​∩⋯∩An​​∣=∣S∣−∑∣Ai​∣+∑∣Ai​∩Aj​∣−∑∣Ai​∩Aj​∩Ak​∣+⋯+(−1)n∣A1​​∩A2​​∩⋯∩An​​∣​

(2)集合 S S S中至少具有性质 P 1 P_{1} P1​， P 2 P_{2} P2​， ⋯ cdots ⋯， P n P_{n} Pn​之一的对象个数为
∣ A 1 ∪ A 2 ∪ ⋯ ∪ A n ∣ = ∑ ∣ A i ∣ − ∑ ∣ A i ∩ A j ∣ + ∑ ∣ A i ∩ A j ∩ A k ∣ + ⋯ + ( − 1 ) n + 1 ∣ A 1 ∩ A 2 ∩ ⋯ ∩ A n ∣ egin{aligned} |A_{1} cup A_{2} cup cdots cup A_{n}|= & sum |A_{i}|-sum |A_{i} cap A_{j}|+sum |A_{i} cap A_{j} cap A_{k}|+cdots+ \ & (-1)^{n + 1}|A_{1} cap A_{2} cap cdots cap A_{n}| end{aligned} ∣A1​∪A2​∪⋯∪An​∣=​∑∣Ai​∣−∑∣Ai​∩Aj​∣+∑∣Ai​∩Aj​∩Ak​∣+⋯+(−1)n+1∣A1​∩A2​∩⋯∩An​∣​
用下面的例3说明容斥原理的应用。
例3：求1 – 2000不能被3、5、9整除的整数个数。
解：设集合 A A A是 S S S中能被3整除的数的集合， B B B是 S S S中能被5整除的数的集合， C C C是 S S S中能被9整除的数的集合。用符号 ⌊ r ⌋ lfloor r
floor ⌊r⌋表示不超过 r r r的最大整数。

∣ A ∣ = ⌊ 2000 3 ⌋ = 666 |A|=lfloorfrac{2000}{3}
floor = 666 ∣A∣=⌊32000​⌋=666， ∣ B ∣ = ⌊ 2000 5 ⌋ = 400 |B|=lfloorfrac{2000}{5}
floor = 400 ∣B∣=⌊52000​⌋=400， ∣ C ∣ = ⌊ 2000 9 ⌋ = 222 |C|=lfloorfrac{2000}{9}
floor = 222 ∣C∣=⌊92000​⌋=222

一个数同时被 x x x和 y y y整除，当且仅当它能被最小公倍数 l c m ( x , y ) lcm(x, y) lcm(x,y)整除，则有

∣ A ∩ B ∣ = ⌊ 2000 l c m ( 3 , 5 ) ⌋ = ⌊ 2000 15 ⌋ = 133 |A cap B|=lfloorfrac{2000}{lcm(3,5)}
floor=lfloorfrac{2000}{15}
floor = 133 ∣A∩B∣=⌊lcm(3,5)2000​⌋=⌊152000​⌋=133

∣ B ∩ C ∣ = ⌊ 2000 l c m ( 5 , 9 ) ⌋ = ⌊ 2000 45 ⌋ = 44 |B cap C|=lfloorfrac{2000}{lcm(5,9)}
floor=lfloorfrac{2000}{45}
floor = 44 ∣B∩C∣=⌊lcm(5,9)2000​⌋=⌊452000​⌋=44

∣ A ∩ C ∣ = ⌊ 2000 l c m ( 3 , 9 ) ⌋ = ⌊ 2000 9 ⌋ = 222 |A cap C|=lfloorfrac{2000}{lcm(3,9)}
floor=lfloorfrac{2000}{9}
floor = 222 ∣A∩C∣=⌊lcm(3,9)2000​⌋=⌊92000​⌋=222

∣ A ∩ B ∩ C ∣ = ⌊ 2000 l c m ( 3 , 5 , 9 ) ⌋ = ⌊ 2000 45 ⌋ = 44 |A cap B cap C|=lfloorfrac{2000}{lcm(3,5,9)}
floor=lfloorfrac{2000}{45}
floor = 44 ∣A∩B∩C∣=⌊lcm(3,5,9)2000​⌋=⌊452000​⌋=44

根据容斥定理，答案为

∣ A ‾ ∩ B ‾ ∩ C ‾ ∣ = S − ( ∣ A ∣ + ∣ B ∣ + ∣ C ∣ ) + ( ∣ A ∩ B ∣ ) + ∣ B ∩ C ∣ + ∣ A ∩ C ∣ − ∣ A ∩ B ∩ C ∣ = 2000 − ( 666 + 400 + 222 ) + 133 + 44 + 222 − 44 = 1067 egin{aligned} |overline{A} cap overline{B} cap overline{C}| & = S-(|A|+|B|+|C|)+(|A cap B|)+|B cap C|+ \ & |A cap C|-|A cap B cap C| \ & = 2000-(666 + 400 + 222)+133 + 44 + 222 – 44 \ & = 1067 end{aligned} ∣A∩B∩C∣​=S−(∣A∣+∣B∣+∣C∣)+(∣A∩B∣)+∣B∩C∣+∣A∩C∣−∣A∩B∩C∣=2000−(666+400+222)+133+44+222−44=1067​

3. 例题

与容斥原理有关的题目，一般要结合其他知识点，然后建模为容斥定理的两种定义，以提高计算的效率。下面用一个比较简单的例子说明这种思路。读者需要做一些习题熟练这种思路，对于和计数有关的问题，如果常用的算法超时，可以考虑用容斥原理加速。下面给出一道例题。

例7 硬币购物（洛谷P1450）
问题描述：有4种硬币，面值分别为 c 1 c_{1} c1​、 c 2 c_{2} c2​、 c 3 c_{3} c3​、 c 4 c_{4} c4​。某人去买东西，去了 n n n次，每次带 d i d_{i} di​枚第 i i i种硬币，想购买 s s s价值的东西，问每次有多少种付款方法？
输入：第1行输入5个整数，分别代表 c 1 c_{1} c1​、 c 2 c_{2} c2​、 c 3 c_{3} c3​、 c 4 c_{4} c4​、 n n n。后面 n n n行中，每行输入5个整数，描述一次购买行为，分别代表 d 1 d_{1} d1​、 d 2 d_{2} d2​、 d 3 d_{3} d3​、 d 4 d_{4} d4​、 s s s。
输出：对于每次购买，输出一个整数，表示答案。
数据范围： 0 ≤ c i 0leq c_{i} 0≤ci​， d i d_{i} di​， s ≤ 100000 sleq100000 s≤100000， 1 ≤ n ≤ 1000 1leq nleq1000 1≤n≤1000。
本题看起来和5.2节的多重背包差不多，区别是这里求方案数（多少种付款方法）。本题即使用二进制拆分优化，也仍然超时。下面用DP结合容斥定理求解。
本题是这样一个问题：
∑ c i x i = s sum c_{i}x_{i}=s ∑ci​xi​=s， x i ≤ d i x_{i}leq d_{i} xi​≤di​
其中， x i x_{i} xi​表示第 i i i种硬币的数量，求 x x x的解有多少种。如果没有 d i d_{i} di​的限制，这是一个完全背包问题，用 d p [ j ] dp[j] dp[j]表示方案数求和为 j j j的解的数量，有 d p [ j ] = d p [ j ] + d p [ j − c [ i ] ] dp[j]=dp[j]+dp[j – c[i]] dp[j]=dp[j]+dp[j−c[i]]，其中 c [ i ] c[i] c[i]为硬币面值。
对于不符合要求的方案，是这样一个问题：
∑ c i x i = s sum c_{i}x_{i}=s ∑ci​xi​=s， x i ≥ d i + 1 x_{i}geq d_{i}+1 xi​≥di​+1

变形得 ∑ c i x i = s − ∑ ( d i + 1 ) sum c_{i}x_{i}=s-sum(d_{i}+1) ∑ci​xi​=s−∑(di​+1)，也可以看作一个完全背包解的数量是 d p [ s − c [ i ] ⋅ ( d [ i ] + 1 ) ] dp[s – c[i]·(d[i]+1)] dp[s−c[i]⋅(d[i]+1)]。
合法方案数 = 无限制方案数 – 不合法方案数。其中，无限制方案数和不合法方案数，经过上面的分析，都是完全背包。但是，不合法方案数，其中一些是有交集的，根据容斥定理第2种定义计算 ∣ A 1 ∪ A 2 ∪ ⋯ ∪ A n ∣ |A_{1} cup A_{2} cup cdots cup A_{n}| ∣A1​∪A2​∪⋯∪An​∣，应该减去有奇数个元素的集合，加上有偶数个元素的集合。
下面给出洛谷P1450的代码，先预处理完全背包，然后对每次测试用容斥定理求解。 另外，在第16行用状态压缩的技巧处理集合，统计集合中元素数量的奇偶。

#include<cstdio>
const int N = 100009;
long long dp[N];
int main() {
            
    int c[4], d[4];
    for (int i = 0; i < 4; i++) scanf("%d", &c[i]);
    dp[0] = 1;
    for (int i = 0; i < 4; i++) //完全背包，预处理
        for (int j = c[i]; j < N; j++)
            dp[j] += dp[j - c[i]];
    int T; scanf("%d", &T);
    while (T--) {
            
        for (int i = 0; i < 4; i++) scanf("%d", &d[i]);
        int s; scanf("%d", &s);
        long long ans = dp[s]; //容斥定理公式的第1项
        for (int i = 1; i <= 15; i++) //0001~1111，二进制数枚举集合
        {
            
            int now = s;
            int tmp = i;
            int ov = 0; //用ov判断奇偶
            for (int j = 0; tmp; j++) //容斥
            {
            
                if (tmp & 1)
                {
            
                    tmp = tmp >> 1;
                    ov =!ov;
                    now -= (d[j] + 1) * c[j]; //tmp找i中的1
                }
                if (now < 0) continue;
                if (ov) ans -= dp[now]; //奇数，减去
                else ans += dp[now]; //偶数，加上
            }
        }
        printf("%lld
", ans);
    }
    return 0;
}

洛谷题解：好巧妙的一道dp题！

如果我们就赤裸裸的多重背包那么就是O(10^5*10^5*1000)

一周的时间都运行不完（手动滑稽）！

那么怎么办呢？如果没有硬币数量的限制那就多好啊？直接一个完全背包预处理，然后O(1)输出就好了

可是有了硬币的限制怎么办？我们先考虑一个简单一点的情况：只有第一个硬币有限制。

如果我们用类似前缀和的思想（术语叫差分），我们先完全背包预处理好无限制的情况，拿dp[tot]减去dp[tot-c[i]*(d[i]+1)]就是我们所需的方案数。

这是为什么呢？为什么要弄个c[i]*(d[i]+1)？其实我们可以这样想，无限制的情况就是没有那个di，而有限制时，不应该计入答案的方案数就是把c[i]这个硬币取了超过d[i]次，对吧？那么我们手动先取出d[i]+1个c[i]的硬币，然后剩下的价值弄个完全背包，这时就是我们所不需要的答案， 把它减掉就行了。

那么对于4个（或更多）的硬币有限制，我们就逐一把4个硬币单独限制的方案数减掉，这时可能会减重了（即同时两个硬币有限制的情况减了两次），所以我们再把4个硬币两两同时限制的方案数加上，可能又加重了，再把4个硬币33同时限制减掉，最后加上4个同时限制的方案数就是我们所需的答案。这就是大名鼎鼎的容斥原理啊！写成位运算就很优美了！

方案数会爆int哟。

【习题】 洛谷P3349/P3270/P4336/P4448/P4491/P5339/P5400/P5664。

Catalan数和Stirling数

1 Catalan数

Catalan数的计算公式涉及组合计数，它是很多组合问题的数学模型，是一个很常见的数列。

1. 定义

Catalan数是一个数列，它的一种定义是
C n = 1 n + 1 ( 2 n n ) , n = 0 , 1 , 2 , ⋯ C_{n}=frac{1}{n + 1}inom{2n}{n}, n = 0,1,2,cdots Cn​=n+11​(n2n​),n=0,1,2,⋯

列举一部分Catalan数：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, …。Catalan数的增长速度极快。
Catalan数有3种计算公式。

公式1： C n = 1 n + 1 ( 2 n n ) = ( 2 n n ) − ( 2 n n + 1 ) = ( 2 n n ) − ( 2 n n − 1 ) C_{n}=frac{1}{n + 1}inom{2n}{n}=inom{2n}{n}-inom{2n}{n + 1}=inom{2n}{n}-inom{2n}{n – 1} Cn​=n+11​(n2n​)=(n2n​)−(n+12n​)=(n2n​)−(n−12n​)。

( 2 n n ) inom{2n}{n} (n2n​)是在 2 n 2n 2n种情况中选 n n n个的组合数； ( 2 n n − 1 ) inom{2n}{n – 1} (n−12n​)是在 2 n 2n 2n种情况选 n − 1 n – 1 n−1个的组合数。注意， ( 2 n n − 1 ) inom{2n}{n – 1} (n−12n​)和 ( 2 n n + 1 ) inom{2n}{n + 1} (n+12n​)等价，公式可以从一个基本模型推导出来：把 n n n个1和 n n n个0排成一行，使这一行的任意前 k k k个数中1的数量总是大于或等于0的数量（或者0的数量大于或等于1的数量，二者等价）。这样的排列有多少个？这样的排列一共有 C n C_{n} Cn​个，即Catalan数。

公式2：递推， C n = C 0 C n − 1 + C 1 C n − 2 + ⋯ + C n − 2 C 1 + C n − 1 C 0 = ∑ k = 0 n − 1 C k C n − k C_{n}=C_{0}C_{n – 1}+C_{1}C_{n – 2}+cdots +C_{n – 2}C_{1}+C_{n – 1}C_{0}=sum_{k = 0}^{n – 1}C_{k}C_{n – k} Cn​=C0​Cn−1​+C1​Cn−2​+⋯+Cn−2​C1​+Cn−1​C0​=∑k=0n−1​Ck​Cn−k​， C 0 = 1 C_{0}=1 C0​=1。

公式3： C n = 4 n − 2 n + 1 C n − 1 C_{n}=frac{4n – 2}{n + 1}C_{n – 1} Cn​=n+14n−2​Cn−1​， C 0 = 1 C_{0}=1 C0​=1。

从公式3可知，当 n n n很大时， C n / C n − 1 ≈ 4 C_{n}/C_{n – 1}≈4 Cn​/Cn−1​≈4。所以Catalan数的增长是 O ( 4 n ) O(4^{n}) O(4n)的，增长极快。

下面说明这3种公式的应用场合。
(1) 公式2的应用场合：公式2的优点是不用算除法，此时 n n n较小，需要输出Catalan数的值，如计算 n ≤ 500 n≤500 n≤500内的Catalan数。编程需要二重循环，复杂度为 O ( n 2 ) O(n^{2}) O(n2)。不过，Catalan数仍然是一个超级大的数。
(2) 公式1和公式3的应用场合： n n n非常大，不能直接输出Catalan数，而是进行取模操作。例如，对第10万个Catalan数取模，用公式2计算就太慢了。用公式1和公式3更快。不过，公式1和公式3有大数除法，需要转换为逆元，然后再取模。先预计算 n n n的阶乘（计算阶乘的同时对阶乘取模），然后再用公式计算。类似的编码，参考第3节的例题代码。

2. 应用

用上述公式解释下面几个应用问题，其中，二叉树问题是公式2的模型，其他问题是公式1的模型。

棋盘问题
一个 n n n行 n n n列的棋盘，从左下角走到右上角，一直在对角线右下方走，不穿过主对角线，走法有多少种？例如， n = 4 n = 4 n=4时，有14种走法。
这个问题就是公式1的模型，下面进行分析。
对方向编号，向上为0，向右为1，那么从左下角走到右上角一定会经过 n n n个1和 n n n个0。满足要求的路线是：走到任意一步 k k k，前 k k k步中向右的步数（1的个数）大于或等于向上的步数（0的个数），否则就穿越对角线了。
设从左下角走到右上角的总路线有 X X X条，分为3部分：对角线下面的 A A A条路线、对角线上面的 B B B条路线、穿过对角线的 C C C条路线。不过，这3部分可以简化为两部分：对角线下面的 A A A、穿过对角线的 Y Y Y（包括 B B B和 C C C）。 A = X − Y A = X – Y A=X−Y就是答案。
总路线 X = ( 2 n n ) X=inom{2n}{n} X=(n2n​)，它的含义是：在 2 n 2n 2n个位置放 n n n个1（剩下的 n n n个肯定是0），这样的数有 ( 2 n n ) inom{2n}{n} (n2n​)个。
对于 Y Y Y，需要用到一种叫作Andre’s Reflection Method的方法。图7.1(a)给出了一条穿过对角线的路线（即 C C C路线；或者给出一条在斜对角上方，并不穿过对角线的路线，即 B B B路线，分析和 C C C路线一样）。在图7.1(b)中，画一条新的对角线，把它画在原来对角线的上面一格。
下面开始操作。原来的路线，从左下角出发，第1次接触到这条新对角线后，把剩下的部分以新对角线为轴进行映射，得到新的路线。这条新的路线即为图7.1(b)中的加粗黑线。加粗黑线下面的一部分黑线是原来的，保持不变；上面一部分是新的，与原来那一部分对称。整个路线仍然是连续的，但是路线的终点变为 ( n − 1 , n + 1 ) (n – 1, n + 1) (n−1,n+1)。注意，“在原对角线右下方不穿过主对角线的走法”，即前文提到的 A A A路线，与新对角线无交集，无法映射，被排除在外。

新的路线和原来的路线是一一对应的。这些新路线有多少条？此时，有 n + 1 n + 1 n+1个0， n − 1 n – 1 n−1个1，共 2 n 2n 2n个；选出 n − 1 n – 1 n−1个1（等价于选出 n + 1 n + 1 n+1个0）的排列，有 Y = ( 2 n n − 1 ) Y=inom{2n}{n – 1} Y=(n−12n​)。可得
A = X − Y = ( 2 n n ) − ( 2 n n − 1 ) A = X – Y=inom{2n}{n}-inom{2n}{n – 1} A=X−Y=(n2n​)−(n−12n​)。
下面给出一道棋盘问题的题目。
例8 树屋的阶梯（洛谷P2532）
问题描述：树屋位于高度为 n + 1 n + 1 n+1的大树上。用钢材搭建一个到树屋的阶梯，钢材的宽和高不同，但都是1的整数倍。可以选 n n n个钢材搭建一个总高度 n n n的阶梯，每级阶梯高度为1。每种钢材数量充足。问有多少种搭建方法？
输入：一个整数 n n n，表示阶梯高度。 1 ≤ n ≤ 500 1≤n≤500 1≤n≤500。
输出：一个整数，表示搭建方法数量。
例如，阶梯高度 n = 3 n = 3 n=3；有5种方法。

本题是棋盘问题，答案是第 n n n个Catalan数，如 n = 3 n = 3 n=3时，第3个Catalan数是5。
n = 500 n = 500 n=500时，Catalan数极大，如果使用C++语言，需要用高精度编程。下面给出Python代码，直接用公式3计算： C n = 4 n − 2 n + 1 C n − 1 C_{n}=frac{4n – 2}{n + 1}C_{n – 1} Cn​=n+14n−2​Cn−1​。

n = int(input())  # 计算第n个Catalan数，注意n从0开始
c = 1
for i in range(1, n + 1):
    c = c * (4 * i - 2) / (i + 1)  # 不能写成c = (4 * i - 2) / (i + 1) * c，浮点数问题导致出错
    # Python 3大整数除法用"//"，不能用"/"，可能溢出
print(c)

括号问题
用 n n n个左括号和 n n n个右括号组成一串字符串，有多少种合法的组合？例如，”()()(())“是合法的，而”())( )”是非法的。显然，合法的括号组合是任意前 k k k个括号组合，左括号的数量大于或等于右括号的数量。
定义左括号为0，右括号为1。问题转换为 n n n个0和 n n n个1组成的序列，任意前 k k k个序列中，0的数量都大于或等于1的数量。模型和上面的棋盘问题一样。
出栈序列问题
例9 栈（洛谷P1044）
问题描述：对给定的 n n n，计算并输出由操作数序列 1 , 2 , ⋯   , n 1,2,cdots,n 1,2,⋯,n经过操作可能得到的输出序列的总数。
输入：一个整数 n n n。 1 ≤ n ≤ 18 1≤n≤18 1≤n≤18。
输出：可能输出序列的总数目。
给定一个以字符串形式表示的入栈序列，问一共有多少种可能的出栈顺序？例如，入栈序列为(123)，则出栈序列一共有5种：(123)、(132)、(213)、(231)、(321)。
分析可知，合法的序列是对于出栈序列中的每个数字，在它后面的、比它小的所有数字，一定是按递减顺序排列的。例如，(321)是合法的，3出栈之后，比它小的后面的数字是(21)，且这个顺序是递减顺序。而(312)是不合法的，因为在3后面的数字(12)，是一个递增的顺序。
对于每个数，必须入栈一次，出栈一次。定义进栈操作为0，出栈操作为1。 n n n个数的所有状态对应 n n n个0和 n n n个1组成的序列。出栈序列，即要求入栈的操作数大于或等于出栈的操作数。问题转换为由 n n n个1和 n n n个0组成的 2 n 2n 2n位二进制数，任意前 k k k个序列，0的数量大于或等于1的数量。结果仍然是Catalan数。
括号问题和出栈序列问题实质上是一样的，括号问题可以用栈来模拟。
二叉树问题
n n n个节点构成二叉树，共有多少种情况？
例如，有3个节点（图中的圆点）的二叉树，可以构成5种二叉树。

这个问题符合公式2的模型，即
C n = C 0 C n − 1 + C 1 C n − 2 + ⋯ + C n − 2 C 1 + C n − 1 C 0 = ∑ k = 0 n − 1 C k C n − k C_{n}=C_{0}C_{n – 1}+C_{1}C_{n – 2}+cdots +C_{n – 2}C_{1}+C_{n – 1}C_{0}=sum_{k = 0}^{n – 1}C_{k}C_{n – k} Cn​=C0​Cn−1​+C1​Cn−2​+⋯+Cn−2​C1​+Cn−1​C0​=∑k=0n−1​Ck​Cn−k​， C 0 = 1 C_{0}=1 C0​=1
其含义如下：
C 0 C n − 1 C_{0}C_{n – 1} C0​Cn−1​：右子树有0个节点，左子树有 n − 1 n – 1 n−1个节点；
C 1 C n − 2 C_{1}C_{n – 2} C1​Cn−2​：右子树有1个节点，左子树有 n − 2 n – 2 n−2个节点；
……
C n − 1 C 0 C_{n – 1}C_{0} Cn−1​C0​：右子树有 n − 1 n – 1 n−1个节点，左子树有0个节点。
5) 三角剖分问题
有 n + 1 n + 1 n+1条边的凸多边形区域，在内部插入不相交的对角线，把凸多边形划分为多个三角形。有多少种方法？方法数是第 n − 1 n – 1 n−1个Catalan数。
【习题】
洛谷P1641/P1722/P1976/P3200/P4769/P3978。

2 Stirling数

Stirling数也是解决特定组合问题的数学工具，包括两种：第1类Stirling数、第2类Stirling数，它们有相似的地方。
首先通过经典的仓库钥匙问题了解第1类Stirling数。
问题描述：有 n n n个仓库，每个仓库有两把钥匙，共 2 n 2n 2n把钥匙，有 n n n位保管员，提出下面两个问题。
问题1：如何分配钥匙，使所有保管员都能够打开所有仓库？
问题2：保管员分别属于 k k k个不同的部门，部门中的保管员数量和他们管理的仓库数量一样多。例如，第 i i i个部门有 m m m个管理员，管理 m m m个仓库。如何分配钥匙，使同部门的所有保管员能打开所有本部门的仓库，但是无法打开其他部门的仓库？
问题1很好解答。1号仓库里放2号仓库的钥匙，2号仓库放3号仓库的钥匙， ⋯ cdots ⋯， n n n号仓库放1号库的钥匙， n n n个仓库形成了一个闭环。然后，每个保管员拿一把钥匙就好了，他打开一个仓库后，就能拿到下一把钥匙，继续打开其他所有的仓库。
问题2是问题1的扩展：把 n n n个仓库分成 k k k个圆排列，每个圆内部按问题1处理。这里的麻烦问题是把 n n n个仓库分配到 k k k个圆里，不能有空的圆，问有多少种分法？答案就是第1类Stirling数。

第1类Stirling数

定义第1类Stirling数 s ( n , k ) s(n, k) s(n,k)：把 n n n个不同的元素分配到 k k k个圆排列里，圆不能为空，有多少种分法？
下面直接给出第1类Stirling数的递推公式 。
s ( n , k ) = s ( n − 1 , k − 1 ) + ( n − 1 ) × s ( n − 1 , k ) s(n, k)=s(n – 1, k – 1)+(n – 1)×s(n – 1, k) s(n,k)=s(n−1,k−1)+(n−1)×s(n−1,k)， 1 ≤ k ≤ n 1≤k≤n 1≤k≤n
s ( 0 , 0 ) = 1 s(0, 0)=1 s(0,0)=1， s ( k , 0 ) = 0 s(k, 0)=0 s(k,0)=0， 1 ≤ k ≤ n 1≤k≤n 1≤k≤n
s ( n , k ) s(n, k) s(n,k)是指数增长的。
根据递推公式计算部分第1类Stirling数，如表7.1所示。

n	s(n,k)
k=0	k=1	k=2	k=3	k=4	k=5	k=6	…
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1
6	0	120	274	225	85	15	1
…
例如：
s ( 2 , 1 ) = 1 s(2, 1)=1 s(2,1)=1，两个物体a、b放在一个圆圈里，有一种方案，即((ab))；
s ( 3 , 1 ) = 2 s(3, 1)=2 s(3,1)=2，3个物体a、b、c放在一个圆圈里，有两种方案，即((abc))和((acb))；
s ( 3 , 2 ) = 3 s(3, 2)=3 s(3,2)=3，3个物体a、b、c放在两个圆圈里，有3种方案，即((ab),©)、((ac),b)、((a),(bc))。

第2类Stirling数

定义第2类Stirling数 S ( n , k ) S(n, k) S(n,k)：把 n n n个不同的球分配到 k k k个相同的盒子里 ，不能有空盒子。有多少种分法？
S ( n , k ) S(n, k) S(n,k)的递推公式为
S ( n , k ) = k S ( n − 1 , k ) + S ( n − 1 , k − 1 ) S(n, k)=kS(n – 1, k)+S(n – 1, k – 1) S(n,k)=kS(n−1,k)+S(n−1,k−1)， 1 ≤ k ≤ n 1≤k≤n 1≤k≤n
S ( 0 , 0 ) = 1 S(0, 0)=1 S(0,0)=1， S ( i , 0 ) = 0 S(i, 0)=0 S(i,0)=0， 1 ≤ i ≤ n 1≤i≤n 1≤i≤n
从递推公式看出， S ( n , k ) S(n, k) S(n,k)是指数增长的，如表7.2所示。

n	S(n,k)
k=0	k=1	k=2	k=3	k=4	k=5	k=6	…
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1

例如：
S ( 2 , 1 ) = 1 S(2, 1)=1 S(2,1)=1，两个球a、b放在一个盒子里，有一种方案，即 { ( a b ) } {(ab)} {(ab)}；
S ( 3 , 1 ) = 1 S(3, 1)=1 S(3,1)=1，3个球a、b、c放在一个盒子里，有一种方案，即 { ( a b c ) } {(abc)} {(abc)}；
S ( 3 , 2 ) = 3 S(3, 2)=3 S(3,2)=3，3个球a、b、c放在两个相同盒子里，有3种方案，即 { ( a b ) , ( c ) } {(ab),(c)} {(ab),(c)}、 { ( a c ) , b } {(ac),b} {(ac),b}、 { ( a ) , ( b c ) } {(a),(bc)} {(a),(bc)}。

下面给出一道模板题。

例10 小朋友的球（洛谷P1655）
问题描述：把 N N N个球放到 M M M个相同的盒子里，要求每个盒子中至少一个球。问有几种放法？
输入：输入多组数据，每行输入两个整数 N N N和 M M M。 1 ≤ N , M ≤ 100 1leq N,Mleq100 1≤N,M≤100。
输出：对每组数据，输出答案。

由于 S ( n , k ) S(n,k) S(n,k)是指数增长的，答案是极大的数字。如果用C++语言，需要处理大数。这里简单地给出Python代码。

N = 105
S = [[0] * N for i in range(N)]
for i in range(1, N):
    S[i][1] = 1
    for j in range(2, i):
        S[i][j] = S[i - 1][j - 1] + j * S[i - 1][j]
while True:  # 多组数据
    try:
        n, k = map(int, input().split()); print(S[n][k])
    except EOFError:
        break

【习题】
Stirling数的应用比较狭窄，常和其他知识点一起出题，参考以下习题。
洛谷P5395/P5396/P5408/P5409/P4827。