组合数学及相关计数法
一、计数原理
1.加法原理
举个例子：从甲地到乙地共有海陆空三种选择，坐船有 $3$ 班，坐车有 $5$ 班，坐飞机有 $2$ 班，问从甲地到乙地共有几种选择？
解：这是一个幼儿园的题 $3+5+2=10$
加法原理（分类计数原理）：完成一件事共有 $n$ 类方法，第一类有 $a_1$ 种方案，第二类有 $a_2$ 种方案，$\cdots$ ，第 $n$ 类有 $a_n$ 种方案，那么完成这一件事一共有$a_1+a_2+\cdots+a_n$ 种方法，注意不重不漏
2.乘法原理
依旧举个例子:从甲地到乙地要途经 $A$ 地，从甲地到 $A$ 地有 $5$ 种方法，从 $A$ 地到乙地有 $3$ 种方法，问从甲地到乙地共有几种选择
解：这个大概要小学水平了 $5\times3=15$
乘法原理（分步计数原理）：完成一件事情需要分 $n$ 步进行，第一步有 $a_1$ 种方案，第二步有 $a_2$ 种方案，$\cdots$ ，第 $n$ 步有 $a_n$ 种方案，那么完成这一件事一共有$a_1 \times a_2 \times \cdots \times a_n$ 种方法，注意不重不漏
3.排列与组合
（1）排列: 从 $n$ 个不同元素中取出 $m(m \le n)$ 个元素，按照一定顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列，用符号 $A(n,m)$ 表示
$A(n,m)=n \times (n-1) \times (n-2) \times \cdots \times (n-m+1)=\dfrac{n!}{(n-m)!}$ （有序）
（2）组合: 从 $n$ 个不同元素中取出 $m(m \le n)$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数，用符号 $C(n,m)$ 表示
$C(n,m)=\dfrac{A(n,m)}{A(m,m)}=\dfrac{n!}{(m!(n-m)!)}$ （无序（去重））
几种常用的策略（方法）：
1）特殊元素和位置优先策略
例：由 $0,1,2,3,4,5$ 可组成多少个没有重复数字的 $5$ 位奇数
解：由于末尾和首位有特殊要求，应优先安排，以免不合要求的元素占了这两个位置。
先安排末位共有 $C(3,1)$，然后按排首位共有 $C(4,1)$，最后排其他位置共有 $A(4,3)$
由分步计数原理得
例：$7$ 人站成一排，其中甲乙相邻，且丙丁相邻，问共有多少种不同的排法？
解：先将甲乙两元素捆绑在一起看作一个复合元素，同时丙丁也看作一个复合元素，再与其他元素进行排列，同时对复合元素内部自排。
例：记者要为 $5$ 名志愿者和他们帮助的 $2$ 位老人们拍照，要求站成一排，$2$ 位老人相邻但不排在两端，求不同排法的数量？
解：第一步排两端，共有 $C(5,1) \times C(5,2)$（或 $A(5,2)$）种排列方式
第二步将两个老人看作一个整体和 $4$ 名志愿者全排列，有 $A(4,4)$ 种排列方式
第三步两个老人内部全排列，有 $A(2,2)$ 种方式
所以得到 $ans=A(5,2) \times A(4,4) \times A(2,2)$ 种排列组合方式
3）不相邻问题插空策略
例：一个晚会的节目有 $4$ 个舞蹈，$2$ 个相声，$3$ 个独唱，舞蹈节目不能连续出场，则节目的出场顺序有多少种？
解：第一步，排列 $2$ 个相声和 $3$ 个独唱，一共有 $A(5,5)$ 种方案
第二步，将 $4$ 种舞蹈插入第一步排好的 $5$ 个元素中间包含首尾两个空位一共有 $A(6,4)$ 种不同的方法
得到 $ans=A(5,5) \times A(6,4)$
不相邻问题通常用插空法：
把要求不相邻的元素放在一边，先排其他的元素，再将不相邻的元素插在已经排好的元素之间的空位上。
4）定序问题倍缩空位插入策略
例：$7$ 人排队，其中甲乙丙 $3$ 人顺序一定，共有多少种排法？
解：共有不同排法个数为 $A(7,7) \div A(3,3)=\dfrac{A(7,7)}{A(3,3)}$
（倍缩法）对于某几个元素顺序一定的排列问题，可以先把这几个元素与其它元素一起排列，然后用总排列数除以这几个元素（固定顺序）的全排列数。
5）排列问题求幂策略
例：把 $6$ 名实 练 习生分配到 $7$ 个车间实 练 习，共有多少种不同的排法？
解：完成此事共需 $6$ 步：
$$
1.把第1名实习生分配出去有7种分发\
2.把第2名实习生分配出去有7种分发\
\cdot\
\cdot\
\cdot\
\cdot\
$$
所以，排法个数为 $7^6$
6）环排问题线排策略
例：$8$ 人围桌而坐，问有多少种排法？
解：围桌而坐与坐成一排的不同点在于，坐圆形没有首尾之分，所以固定一人，并从此位置开始把圆形展成直线其余 $7$ 人一共有 $(8-1)!=7!$ 种排法
一般地，$n$ 个不同元素做圆形排列，一共有 $(n-1)!$ 种排法
如果从 $n$ 个不同元素中取出 $m$ 个元素作圆形排列，共有 $\dfrac{A(n, m)}{m}$ 种排法
7）多排问题直排策略
例：$8$ 人排成前后两排，每排 $4$ 人，其中甲乙在前排，丙在后排，问共有多少种排法？
解：$8$ 人排成前后两排，相当于 $8$ 人坐 $8$ 把椅子，可以把椅子排成一排
前排有两个特殊元素，方案数为 $A(4,2)$
后 $4$ 个位置上有一个特殊元素，方案数为 $A(4,1)$
其余 $5$ 个人在 $5$ 个位置上任意排列，方案数为 $A(5,5)$
所以一共有 $A(4,2) \times A(4,1) \times A(5,5)$ 种方案
8）排列组合混合问题先选后排策略
例：有 $5$ 个不同的小球，装入 $4$ 个不同的盒子里，每个盒子至少中一个球，共有多少种不同的装法？
解：第一步从 $5$ 个球中选出 $2$ 个元素组成复合元素一共有 $C(5,2)$ 种方法，再把 $4$ 个元素（其中有 $1$ 个复合元素）装入 $4$ 个不同的盒子里一共有 $A(4,4)$ 种方法
由乘法原理知 $ans=C(5,2) \times A(4,4)$
9）平均分组问题除法策略
例：$6$ 本不同的书平均分成 $3$ 组，每组 $2$ 本，问一共有多少种分发？
解：分三步取书得一共有 $C(6,2) \times C(4,2) \times C(2,2)$ 种分发，但是其中每一种不同的分发都被重复计算了 $A(3,3)$ 次
所以最终答案为 $\dfrac{C(6,2) \times C(4,2) \times C(2,2)}{A(3,3)}$
10）重排列
例：由 $4$ 面红旗，$3$ 面蓝旗，$2$ 面黄旗，$5$ 面绿旗排成的一排彩旗共有多少种
解：将 $14$ 面彩旗排成一个排列，方案数为 $A(14,14)$，其中 一种彩旗 之间的每种排列等价
所有一共有 $\dfrac{A(14,14)}{A(4,4) \times A(3,3) \times A(2,2) \times A(5,5)}$ 种
常用结论：
将一个长度为 $n$ 的序列划分成 $m$ 段非空子串的方案数为 $C(n-1,m-1)$,相当于在 $n-1$ 个空位中选择 $m-1$ 个插入隔板的方案数
将一个长度为 $n$ 的序列划分成 $m$ 段可空子串的方案数为 $C(m+n-1,m-1)$,相当于在 $m+n-1$ 个空位中选择 $m-1$ 个插入隔板的方案数
11）错位排序
错排问题指考虑一个有 $n$ 个元素的排列，若一个排列中所有的元素在不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。$n$ 个元素的错排数记为 $D(n)$。研究一个排列错排个数的问题，叫做错排问题或称为更列问题。
这看上去就是一个递推问题，那么递推式是如何推出来的呢？当 $n$ 个编号元素放在 $n$ 个编号位置，元素编号与位置编号各不对应的方案数用 $D(n)$ 表示，那么 $D(n-1)$ 就表示 $n-1$ 个编号元素放在 $n-1$ 个编号位置，各不对应的方案数，其他类推。
第一步，把第 $n$ 个元素放在一个位置，比如位置 $k$，一共有 $n-1$ 种方法
第二步，放编号为 $k$ 的元素，这时有两种情况：
（1）把它放到位置 $n$ ，那么，对于剩下 $n-1$ 个元素，由于第 $k$ 个元素放到了位置 $n$，剩下的 $n-2$ 个元素就有 $D(n-2)$ 种方法；
（2）它不放到位置 $n$，这时，对于这 $n-1$ 个元素，有 $D(n-1)$ 种方法。
综上得到 $D(n)=(n-1) \times (D(n-2)+D(n-1))$
特殊的，$D(1)=0,D(2)=1$
4.组合数取模（Lucas定理）
题：求组合数
法一：递推法，递推式为 $C(n, m)=C(n-1, m)+C(n-1,m-1)$
法二：用公式（ $C(n, m)=\dfrac{n!}{(m!(n-m)!)}$ ）
用 $f[x]$ 存 $x! \mod p$（ $f[x]=(f[x-1]*x) \mod p$ ）
用 $g[x]$ 存 $(x^{-1}) \mod p$（ $g[x]=(g[i-1]*pow(x, p-2)) \mod p$ ）
得到 $C(n, m)=(f[n] \times g[n-m] \times g[m]) \mod p$
Lucas定理：
$$
C(n, m)=(C(n/p,m/p) \times C(n%p, m%p)) \mod p
$$
代码：
long long f[maxn], g[maxn];
long long qpow(long long a, long long b){
long long res=1;
while(b){
if(b&1){ res=(res*a)%MOD; }
a=(a*a)%MOD;
b>>=1;
}
return res%MOD;
}
void init(){
f[0]=g[0]=1;
for(int i=1;i<MOD;i++){
f[i]=(f[i-1]*i)%MOD;
g[i]=(g[i-1]*qpow(i, MOD-2))%MOD;
}
}
long long C(long long n, long long m){
if(n<m) return 0;
return ((f[n]*g[n-m])%MOD*g[m])%MOD;
}
long long Lucas(long long n, long long m){
if(m==0) return 1;
if(n<m) return 0;
return (Lucas(n/MOD, m/MOD)*C(n%MOD, m%MOD))%MOD;
}
5.中国剩余定理（CRT）
算法简介
中国剩余定理可以解决如下问题（其中 $m_1,m_2,\cdots,m_n$ 是两两互质整数）：
$$
\begin{cases}x \equiv r_1 (\mod m_1)\x \equiv r_2 (\mod m_2)\\vdots\x \equiv r_n (\mod m_n)\\end{cases}
$$
求 $x$ 的最小非负整数解。
定理过程
1.计算所有模数的积 $M=m_1 \times m_2 \times\cdots\times m_n$
2.对于第 $i$ 个方程：
a.计算 $c_i=\frac{M}{m_i}$
b.计算 $c_i$ 在模 $m_i$ 意义下的逆元 $c_i^{-1}$。（逆元一定存在，因为 $c_i$ 中已经把 $m_i$ 除掉了）
3.方程组的唯一解为 $x=\sum\limits_{i=1}^n r_i \times c_i \times c_i^{-1} \mod M$
代码
long long n, a[105], b[105];
long long exgcd(long long a, long long b, long long &x, long long &y){
if(b==0){
x=1, y=0;
return a;
}
long long x1, y1, d=exgcd(b, a%b, x1, y1);
x=y1, y=x1-a/b*y1;
return d;
}
long long CRT(long long m[], long long r[]){
long long M=1, ans=0;
for(int i=1;i<=n;i++){ M*=m[i]; }
for(int i=1;i<=n;i++){
long long c=M/m[i], x, y;
exgcd(c, m[i], x, y);
ans=(ans+((r[i]*c)%MOD*x)%MOD)%MOD;
}
return (ans%MOD+MOD)%MOD;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
cout<<CRT(a, b);
return 0;
}
6.扩展中国剩余定理
算法简介
扩展中国剩余定理可以解决以下问题：
$$
\begin{cases}x \equiv r_1 (\mod m_1)\x \equiv r_2 (\mod m_2)\\vdots\x \equiv r_n (\mod m_n)\\end{cases}
$$
其中 $m_1,m_2,\cdots,m_n$ 不一定为两两互质的整数，求 $x$ 的最小非负整数解（此时中国剩余定理已经不行了）
算法过程
前两个方程：$x \equiv r_1 (\mod m_1),x \equiv r_2 (\mod m_2)$ 可以转化为不定方程：$x=m_1 \times p+r_1=m_2 \times q+r_2$ 则 $m_1p-m_2q=r_2-r_1$
由裴蜀定理知：
$$
当 gcd(m_1,m_2) \nmid (r_2-r_1)，无解\
当 gcd(m_1, m_2) \mid (r_2-r_1)，有解
$$
由扩欧算法，得特解 $p= p \times \frac{r_2-r_1}{\gcd},q=q \times \frac{r_2-r_1}{\gcd}$，通解 $P=p+\frac{m_2}{\gcd} \times k,Q=q-\frac{m1}{\gcd} \times k$
所以 $x=m_1 \times P+r_1=\frac{m_1 \times m_2}{\gcd} \times k+m_1 \times p+r_1$
前两个方程等价合并为一个方程 $x \equiv r (\mod m)$，其中 $r=m_1 \times p+r_1,m=lcm(m_1, m_2)$
所以 $n$ 个同余方程只要合并 $n-1$ 次，即可求解。
代码
long long n, m[maxn], r[maxn];
long long exgcd(long long a, long long b, long long &x, long long &y){
if(b==0){
x=1, y=0;
return a;
}
long long x1, y1, d=exgcd(b, a%b, x1, y1);
x=y1, y=x1-a/b*y1;
return d;
}
long long EXCRT(long long m[], long long r[]){
long long m1=m[1], m2, r1=r[1], r2, p, q;
for(int i=1;i<=n;i++){
m2=m[i], r2=r[i];
long long t=exgcd(m1, m2, p, q);
if((r2-r1)%t) return -1; // 无解
p=p*(r2-r1)/t;
p=(p%(m2/t)+m2/t)%(m2/t);
r1=m1*p+r1, m1=m1*m2/t;
}
return (r1%m1+m1)%m1;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>m[i]>>r[i];
}
cout<<EXCRT(m, r);
return 0;
}
7.容斥原理
集合的并
| 竞赛学科 | 数学 | 物理 | 化学 | 数学、物理 | 物理、化学 | 数学、化学 | 数学、物理、化学 |
|---|---|---|---|---|---|---|---|
| 人数 | 5 | 6 | 5 | 3 | 2 | 2 | 1 |
问题：一个班里参加数理化竞赛的人数情况如图，求班里参加竞赛的人一共有多少个？
解：把参加数学、物理、化学竞赛的学生集合分别用 $A、B、C$ 表示，则学生总数为 $\left|A \cup B \cup C \right|$。如果把这三个集合的元素个数 $\left|A\right|$，$\left|B\right|$，$\left|C\right|$ 直接加起 来，就会有一些元素重复统计了，因此要减去 $\left|A \cap B\right|$，$\left|A \cap C\right|$，$\left|B \cap C\right|$，但这样又会有一部分多减去了，所以还要加 $\left|A \cap B \cap C\right|$。
所以 $Ans=\left|A \cup B \cup C \right|- \left|A \cap B\right|-\left|A \cap C\right|-\left|B \cap C\right|+\left|A \cap B \cap C\right|$。
对于这道题，$Ans=10$。
总结：对于 $A_1,A_2,\cdots,A_n$ 这 $n$ 个集合，他们的并集元素个数是：
$$
\left| \bigcup_{i=1}^{n} A_i \right|=\sum_{i=1}^{n} \left| A_i \right|-\sum_{i<j}^n \left|A_i \cap A_j\right|+\sum_{i<j<k}^n \left|A_i \cap A_j \cap A_k\right|-\cdots+(-1)^{n-1} \times \left|A_1 \cap A_2 \cap\cdots\cap A_n\right|
$$
例题：
给定一个整数 $n$ 和 $m$ 个不同质数：$p_1,p_2,\cdots,p_m$。
请你求出 $1 \sim n$ 中能被 $p_1,p_2,\cdots,p_m$ 中至少一个数整除的整数有多少个。
解析：
容斥原理，考察能被 $p_i(1 \le i \le m)$ 整除的数的个数为 $\lfloor\frac{n}{p_i}\rfloor$，结果加上这些数量，但是会有重复比如可以同时被两个质数 $p_i,p_j(1 \le i,j \le m)$ 整除的数据被算了两次，需要减去，$\cdots$，因此最终的答案：
$$
Ans=\sum_{i}^n \lfloor\tfrac{n}{p_i}\rfloor-\sum_{i,j}^n \lfloor\tfrac{n}{p_i \times p_j}\rfloor+\sum_{i,j,k}^n \lfloor\tfrac{n}{p_i \times p_j \times p_k}\rfloor-\cdots
$$
时间复杂度：一共有 $2^m-1$ 项相加减，每次计算主要是质数相乘，最多相乘 $m-1$ 次，因此时间复杂度为 $O(2^m \times m)$。