【蓝桥杯】组合数学旧文
计数原理：加法原理
加法原理： 集合 $S$ 被分成两两不相交的部分 $S_1, S_2, S_3, …, S_m$，那么 $S$ 的对象数目等于：$|S| = |S_1| + |S_2| + |S_3| + … + |S_m|$
例： 一个学生想学一门数学课，一门文化课，但不能同时选，现在从 $4$ 门数学课和 $4$ 门文化课中选，一共有 $4 + 4 = 8$ 种方法选一门课。
加法原理的关键是将计数分解为若干个独立（不相容）的部分，保证既不重复也不遗漏地进行计数。 加法原理是利用完备事件组的一个体现，我们可以利用一个集合的补记做题。
例题：分割立方体 lanqiaoOJ 题号 1620
题目描述： 一个立方体，边长为 $n$，分割成 $n × n × n$ 个单位立方体。任意两个单位立方体，或者有 $2$ 个公共点，或者有 $4$ 个公共点，或者没有公共点。请问，没有公共点和有 $2$ 个公共点的立方体，共有多少对？
输入描述： 一个整数 $n，1 \leq n \leq 30$
思路： 反过来计算，先算出有 $4$ 个公共点的立方体有多少对，然后用总对数减去。分几种情况讨论：
-
正方体和周围 $3$ 个正方体相邻，这种情况共有 $8$ 个，就是顶角上的 $8$ 个，总个数 $3 \times 8$；
-
正方体和周围 $4$ 个正方体相邻，这种情况共有 $(n-2) \times 12$ 个 （棱）总个数 $4 \times (n-2) \times 12$；
-
正方体和周围 $5$ 个正方体相邻，这种情况共有 $6 \times (n \times n - 4 \times n + 4)$ 个，总个数 $5 \times 6 \times (n \times n - 4 \times n + 4)$；
-
正方体和周围 $6$ 个正方体相邻，这种情况共有 $(n \times n \times n - n \times n \times 6 + n \times 12 - 8)$ 个，总个数 $6 \times (n \times n \times n - n \times n \times 6 + n \times 12 - 8)$； 最后把这 $4$ 个情况求和再除以 $2$。
正方体一共 $n^3$ 个，共有 $\frac{n^3(n^3 - 1)}{2}$ 种关系
-
正方体和周围 $3$ 个正方体相邻，总个数 $3 \times 8$；
-
正方体和周围 $4$ 个正方体相邻，总个数 $4 \times (n-2) \times 12$；
-
正方体和周围 $5$ 个正方体相邻，总个数 $5 \times 6 \times (n \times n - 4 \times n + 4)$；
-
正方体和周围 $6$ 个正方体相邻，总个数 $6 \times (n \times n \times n - n \times n \times 6 + n \times 12 - 8)$；
-
最后把这 $4$ 个情况求和再除以 $2$。
#include
using namespace std;
int main(){
int n; cin >> n;
if(n == 1){ // 边长为 1 时特判
cout 令 $S$ 是对象的有序对 $(a, b)$ 的集合，其中第一个对象 $a$ 来自大小为 $p$ 的一个集合，对于对象 $a$ 的每个选择，对象 $b$ 有 $q$ 个选择，那么 $S$ 的大小：$|S| = p \times q$
例：中性笔的长度有 $3$ 种，颜色有 $4$ 种，直径有 $5$ 种。不同种类的中性笔有：$3 \times 4 \times 5 = 60$ 种。
例：$34 \times 55 \times 72 \times 113$ 的正整数因子有多少？答：这是算数基本定理的概念。$3$ 有 $0$ ~ $4$ 这 $5$ 种选择，$5$ 有 $6$ 个选择，$7$ 有 $3$ 个选择，$11$ 有 $4$ 个选择，因子总数是 $5 \times 6 \times 3 \times 4 = 360$ 种。
## 排列数
排列是有序的。
不可重复排列数：从 $n$ 个不同的物品中取出 $r$ 个，排列数为：
$\mathrm{A_{n}^{r}=n(n-1)(n-2)…(n-r+1)=\frac{n!}{(n-r)!}}$
可重复排列数，从 $n$ 个不同的物品中可重复地取出 $r$ 个的排列数为：$n^r$。
## 组合数
排列是有序的，组合是无序的。
如果 $S$ 中的元素都不相同，组合数：
$\mathrm{C_{n}^{r}={\binom{n}{r}}={\frac{A_{n}^{r}}{r!}}={\frac{n!}{r!(n-r)!}}}$
## 糊涂人寄信 lanqiaoOJ 题号 1622
**题目描述：** 有一个糊涂人，写了 $n$ 封信和 $n$ 个信封，到了邮寄的时候，把所有的信都装错了信封。求装错信封可能的种类数。
**输入描述：** 每行输入一个正整数 $n$，表示一种情况。$(n \leq 20)$
**输出描述：** 输出相应的答案。
### 解题思路：
题目建模为：有 $1 \sim n$ 个数字，分别放在 $n$ 个位置，问都放错的情况有多少种。
用 DP 来做。定义 $dp[]$，$dp[i]$ 表示数字 $1 \sim i$ 都放错的种类数。$dp[n]$ 是答案。
下面考虑状态转移方程，从 $1 \sim i$ 递推到 $i$。
数字 $i$ 如果放错，有 $i-1$ 个位置可以放，假设其放在第 $k$ 个位置。对于数字 $k$，可以放在 $i$ 位置也可以不放在 $i$ 位置。
如果 $k$ 放在 $i$ 位置，那么对于剩下 $i-2$ 个数字放的次数，就是 $i-2$ 个数字都放错的方法数 $dp[i-2]$。
如果 $k$ 不放在 $i$ 位置，和 $i-1$ 个数字放错的情况相同，为 $dp[i-1]$。
状态转移方程：$dp[i] = (i-1) \times (dp[i-1] + dp[i-2])$
```cpp
#include
using namespace std;
typedef long long ll;
ll dp[30];
int main(){
dp[1]= dp[0]=0;
dp[2]=1;
for(int i=3;i>n) cout>n)功能一样
n = int(n)
print(f(n))import java.util.Scanner;
public class Main {
static long[] dp = new long[30];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
dp[1] = dp[0] = 0;
dp[2] = 1;
for (int i = 3; i 鸽巢原理，又称抽屉原理。
**鸽巢原理：** 把 $n+1$ 个物体放进 $n$ 个盒子，至少有一个盒子包含 $2$ 个或更多的物体。
- 例：在 $370$ 人中，至少有 $2$ 人生日相同；
- 例：$n$ 个人互相握手，一定有 $2$ 个人握手次数相同。
例：$n$ 个人互相握手，一定有 $2$ 个人握手次数相同。 每人跟其他人握手，最少可以是 $0$ 次，最多可以是$n-1$次。 如果握手最少的是 $0$ 次，那么剩下的$n-1$人中，握手最多的人不会超过$n-2$次。$0 \sim n-2$ 共$n-1$种情况。 如果握手最少的张三是 $1$ 次，那么剩下的$n-1$人中，握手最多的李四除了跟张三握手一次，跟其他$n-2$人最多握手$n-2$次，李四最多握手$n-1$次。$1 \sim n-1$ 共$n-1$种情况。 如果握手最少的张三是 $2$ 次，那么剩下的$n-1$人中，握手最多的李四除了跟张三握手一次，跟其他$n-2$人最多握手$n-2$次，李四最多握手$n-1$次。$2 \sim n-1$ 共$n-2$种情况。 …… 所以握手次数最多有$n-1$种情况，最少只有 $1$ 种情况。 把最多的$n-1$种情况看成$n-1$个抽屉，$n$个人放进这$n-1$个抽屉，至少有一个抽屉里面有 $2$ 人。
## 例题：小蓝吃糖果 lanqiaoOJ 题号 1624
**题目描述：** Gardon 有 $n$ 种糖果，每种数量已知。Gardon 不喜欢连续 $2$ 次吃同样的糖果。问有没有可行的吃糖方案。
**输入：** 第一行是整数 N，$0 < n < 1000000$，第二行是 $n$ 个数，表示 $n$ 种糖果的数量 $m_i$，$0 < m_i < 1000000$
**输出：** 输出一行，包含一个 “Yes” 或 “no”。
## 解题思路
继续处理格式，鸽巢原理，用“隔板法”求解。
找出最多的一种糖果，把它的数量 $K$ 看成 $K$ 个隔板，隔成 $K$ 个空间（把每个隔板的右边看成一个空间）；其它所有糖果的数量为 $S$。
最多的一种糖果，把它的数量 $K$ 看成 $K$ 个隔板，隔成 $K$ 个空间（把每个隔板的右边看成一个空间）；其它所有糖果的数量为 $S$。
- （1）如果 $S
```cpp
#include
using namespace std;
int a[1005000];
int main(){
long long sum=0;
int Max=0;
int n; scanf("%d",&n);
for(int i=1;iMax) Max=a[i]; //最多的一种糖果
}
if(sum-Max+1>=Max) printf("Yes\n");
else printf("No\n");
return 0;
}n=int(input())
a=list(map(int,input().split()))
if sum(a)-max(a) max) {
max = x;
}
}
if (sum - max + 1 >= max) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}二项式定理和杨辉三角
杨辉三角：排列成如下三角形的数字
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1每个数是它上面 $2$ 个数的和。
求杨辉三角第 $n$ 行的数字，可以模拟这个推导过程，逐级递推，复杂度 $O(n^2)$。
用数学公式计算，可以直接得到结果，这个公式是$(1 + x)n$。
二项式系数就是$(1 + x)^n$ 展开后第 $r$ 项的系数。
$\mathrm{C_{n}^{r}={\binom{n}{r}}=\frac{n!}{r!(n-r)!}}$
对应杨辉三角的第 $n$ 行第 $r$ 个数是
例：杨辉三角的第 $4$ 行是“$1 3 3 1$”，
$\mathrm{C_{n-1}^{r-1}=C_{4-1}^{1-1}=C_3^0=1、C_3^1=3、C_3^2=3、C_3^3=1}$
理解：$(1 + x)^n$ 的第 $r$ 项，就是从 $n$ 个 $x$ 中选出 $r$ 个，这就是组合数的定义
当 n 较大，且需要取模时，二项式系数有两种计算方法：
（1）递推公式：$\mathrm{C_{n}^{r}=C_{n-1}^{r}+C_{n-1}^{r-1}}$
公式是杨辉三角的定义，即“每个数是它上面 $2$ 个数的和”。计算复杂度是 $O(n^2)$。
（2）用逆直接计算
因为输出取模，那么不用递推公式，直接用公式计算更快。不过，由于除法不能直接取模，需要用到逆。用逆计算二项式系数，有：
$\mathrm{C_{n}^{r}={\binom{n}{r}}=\frac{n!}{r!(n-r)!}}$
$\mathrm{C_{r}^{n}\bmod m=\frac{n!}{r!(n-r)!}\bmod m=(n!\bmod m)((r!)^{-1}\bmod m)(((n-r)!)^{-1}\bmod m)\bmod m}$
用逆计算二项式系数，复杂度是 $O(n)$ 的。
本文由 lggyx 原创，首发于lggyx.github.io。
采用 CC BY-NC-SA 4.0许可协议：转载请注明出处，非商业使用，相同方式共享。