关于“浅谈”

• 真的很浅，不是 NOI WC 的那种《浅谈》
• 难度（应该）不超过蓝题，没有重工业/高科技

基础原理

计数原理

• 加法原理：如果做一件事情有两类方式，第一类方式有 $n$ 种方法，第二类方式有 $m$ 种方法，那么做这件事情总共有 $n+m$ 种方法。
• 乘法原理：如果做一件事情分为两步，第一步有 $n$ 种方法，第二步有 $m$ 种方法，那么做这件事情总共有 $n\times m$ 种方法。

恭喜你，现在，你已经掌握了计数的基本原理了，就让我们看一看下面这个简单的例子，来把我们刚刚学到的东西运用到实践中吧！

• P5291 【省选联考2019】希望

二项式定理

• $(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i$

Lucas 定理

• $C_{n}^m\equiv C_{n\%p}^{m\%p}C_{n/ p}^{m/p}~(m od ~p)$

需要背过的组合数恒等式

0. $C_{n}^m=0 ~(n<0 ~ or ~m<0)$

• 不合法

1. $C_n^m=C_n^{(n-m)}$

• 选 $m$ 个等效于不选另外 $n-m$ 个

2. $C_n^m=\frac{n}{m}C_{(n-1)}^{(m-1)}$

• 分子分母分别补上对应系数

3. $C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}$

• 帕斯卡定理
• 考虑选不选最后一个

4. $\sum_{i=0}^{n} C_n^i=2^n$

• $n$ 个元素的所有子集
• 组合数的和
• 二项式定理 $(1+1)^n$

5. $\sum_{i=0}^{n}(-1)^iC_n^i=[n=0]$

• 二项式定理 $(1-1)^n$

6. $\sum_{k=0}^n k\times C_{n}^k=n \times2^{n-1}$

• 组合数加权和
• 利用第二条恒等式推出

7. $\sum_{i=0}^m C_n^i C_m^{m-i}=C_{n+m}^m$

• 范德蒙德卷积
• 每一种选法都与两个集合合并后的一种选法一一对应

8. $\sum_{i=0}^n C_n^i C_n^i=C_{2n}^{n}$

• 范德蒙德卷积 $n=m$ 的特殊情况

9. $\sum_{i=0}^n C_i^m=C_{n+1}^{m+1}$

• 范德蒙德恒等式
• $n+1$ 个元素选 $m+1$ 个，枚举最后一个元素选什么
• $\sum_{i=0}^n C_i^m=\sum_{i=m}^n C_i^{m}=C_m^m+C_{m+1}^m+\cdots+C_n^m$ $=C_{m+1}^{m+1}+C_{m+1}^{m}+\cdots+C_n^m=C_{m+2}^{m+1}+C_{m+2}^m+\cdots+C_n^m=C_{n+1}^{m+1}$

10. $\sum_{i=s}^n C_i^m=\sum_{i=0}^n C_i^m-\sum_{i=0}^{s-1} C_i^m=C_{n+1}^{m+1}-C_{s}^{m+1}$

• 范德蒙德恒等式引理

插板法

是一种思想，应用较广，用两个例题来理解

• 问题 1：有 $n$ 个完全相同的元素，要求将其分为 $k$ 组（组间有序），每组至少有一个元素，一共有多少种分法？
• 转化问题，$n$ 个元素分成 $k$ 组，可以视作将 $n$ 个元素排成 一列，然后在其中的 $n-1$ 个间隔中选择 $k−1$ 个间隔插入隔板，答案为 $C_{n-1}^{k-1}$
• 也可以看作整数拆分方案数，即把 $n$ 拆分成不为 0 的 $k$ 个数的方案数
• 问题 2：有 $n$ 个完全相同的元素，要求将其分为 $k$ 组（组间有序），每组可以为空，一共有多少种分法？
• 考虑每组“借”一个元素进来，就变成了 $n + k$ 个元素分成 $k$ 组，每组至少有一个元素的情况，原问题和新问题的解一一对应，答案相同，根据问题 1 得答案为 $C_{n+k-1}^{k-1}$
• 同样可以看作把 $n$ 拆分为可以为 0 的 $k$ 个数的方案数

常见定理及引理

圆排列

• $Q_n^m=\frac{A_n^m}{m}$

多重集上的排列组合

• 多重集上的排列常见，多重集上的组合不常见且难度过大，这里只讲多重集上的排列
• 是指将多重集 $S$ 的元素任意排列得到的不同有序序列个数，实际就是有重复元素的排列数（无重复元素就是 $A_{n}^n$）
• 也就是：$\frac{{A_{n}^n}}{\Pi !n_{i}}$
• 例题：把有标号五个人分配到有标号三个村子，其中一个村子分配一个人，两个村子分配两个人，问有多少种分法？（禁止使用斯特林数）
• 第一步：利用多重集排列去除村子的标号，即求 $1,2,2$ 三个数有几种本质不同的排列，得到因子 $\frac{!3}{!2}=3$
• 第二步：五个人里选两个去第一个村庄，剩下的三个人里再选两个去第二个村庄，剩下的一个人里再选一个去第三个村庄，得到因子 $C_{5}^2C_{3}^2C_{1}^1$
• 乘法原理得到答案 $90$

错排列

• 错位排列：对于一个长度为 $n$ 的有序排列 $P_i$ ，如果满足 $P_i\neq i$，则称 $P$ 是 $n$ 的错位排列，即每个元素都不能在其原来位置的排列
• 考虑错排的计算公式，设 $f_n$ 为长度为 $n$ 的错位排列个数，$f_1 = 0，f_2 = 1$ 考虑在长度为 $n-1$ 的错排列基础上再加一个数
  • 如果第 $n$ 个数与前 $n-1$ 个数中的某一个恰好互换来了位置，有两个数被定住，剩下的数显然是一种错排，方案数为 $(n-1)f_{n-2}$
  • 否则，钦定 $n$ 这个数放在前 $n-1$ 个位置中的某个地方，前 $n-1$ 个数中除了那个被占位置的数不能根 $n$ 交换位置的数（这样就变成第一种情况了）剩下的数都只需要保证不在原来的位置，所以这又是一个错排，方案数为 $(n-1)f_{n-1}$
• 综上，$f_{n}=(n-1)(f_{n-1}+f_{n-2})$

斯特林数

基本不考，但是早晚会有用

• 第一类斯特林数：
  • $1-n$ 排列有 $m$ 个环
  • $S_{1}(n,m)=S_{1}(n-1,m-1)+S_{1}(n-1,m)*(n-1)$
• 第二类斯特林数：
  • $n$ 个不同球放到 $m$ 个相同盒子且盒子非空的方案数
  • $S_{2}(n,m)=S_{2}(n-1,m-1)+S_{2}(n-1,m)*m$

鸽巢原理

• 对于一般形式，若将 $n$ 个物体，划分为 $k$ 组，那么至少存在一个分组，含有大于或等于 $\lceil \frac{n}{k} \rceil$ 个物品
• 人话：往五个抽屉里放六只 FDsama，那么至少有一个抽屉里有两个 FDsama
• 没啥用，了解就行，不了解也行

卡特兰数

• 到底什么是卡特兰数？
• 卡特兰数是一种特殊数列，是若干解有关于系数 $n$ 的计数问题的的答案序列
  • 1. 有 $2n$ 个人排成一行进入剧场。入场费 5 元。其中只有 $n$ 个人有一张 5 元钞票，另外 $n$ 人只有 10 元钞票，剧院无其它钞票。 问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
  • 2. 方格图左下角为 $(0,0)$ 右上角为 $(n,n)$ ，从左下角开始每次都只能向右或者向上走一单位，不走到对角线 $y=x$ 上方的情况下到达右上角有多少可能的路径？
  • 3. 一个栈的进栈序列为 $1,2,3,4\dots n$ ，有多少个不同的出栈序列？
  • 4. ...

• 以上所有问题，答案序列都是：$1,1,2,5,14,42,132$
• 如果打表发现形如这样的序列，可考虑卡特兰数
• 卡特兰数的公式有一车，但通常只记这一个就够用了：$H_n=\binom{2n}{n}-\binom{2n}{n-1}$

• 考虑用第二个实例的实际意义推出这个公式：
  • 有一个大小为 $n \times n$ 的方格图左下角为 $(0, 0)$ 右上角为 $(n, n)$，从左下角开始每次都只能向右或者向上走一单位， 不走到对角线 $y = x$ 上方（但可以触碰）的情况下到达右上角有多少可能的路径
  • 不考虑限制的总方案数：$C_{2n}^n$ （总步数为 $2n$，其中向上的个数为 $n$）
  • 将对角线向上平移一格，显然碰到平移后的线与违法是充要的
  • 将目标点 $(n,n)$ 沿平移后的直线翻折到 $(n-1,n+1)$，发现走到 $(n-1,n+1)$ 的方案对称后与违法方案一一对应，所以违法方案数为 $C_{2n}^{n-1}$
  • 故合法方案数为 $C_{2n}^n-C_{2n}^{n-1}$

容斥原理

• 臭名昭著的问题：
• 信竞队有 $n$ 名同学，其中有 $a$ 个人说批话，有 $b$ 个人是 fake 侠，有 $c$ 个人是 FDsama，有 $d$ 个人既说批话又是 fake 侠，有 $e$ 个人既说批话又是 $FDsama$，有 $f$ 个人既是 fake 侠又是 FDsama，有 $g$ 个人既说批话，又是 fake 侠，又是 FDsama，问 $n$ 的值。
• 简单来说，就是对 $2^{n}-1$种非空的交集求和，系数为 $(−1)^{取出集合大小−1}$

• 形式化地写
• $|S_1 \cup S_2 ∪ \cdots ∪ S_n|=\sum|S_i|-\sum|S_i\cap S_j|+\cdots+(-1)^{n-1}|S_1\cap S_2\cap \cdots \cap S_n|$ -$|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{i=1}^{n} (-1)^{i-1} \sum |A_{p_{i,1}} \cap A_{p_{i,2}} \cap \cdots \cap A_{p_{i,i}}|$

• 证明：$Cnt$ 是某个元素被统计进入答案的总次数，$m$ 是包含这个元素的集合个数，则：

$$\begin{aligned} Cnt=&|\{T_i\}|-|\{T_i\cap T_j|i<j\}|+\cdots+(-1)^{k-1}\left|\left\{\bigcap_{i=1}^{k}T_{a_i}|a_i<a_{i+1}\right\}\right|\\ &+\cdots+(-1)^{m-1}|\{T_1\cap\cdots\cap T_m\}|\\ =&\dbinom{m}{1}-\dbinom{m}{2}+\cdots+(-1)^{m-1}\dbinom{m}{m}\\ =&\dbinom{m}{0}-\sum_{i=0}^m(-1)^i\dbinom{m}{i}\\ =&1-(1-1)^m\\ =&[m=0] \end{aligned}$$

二项式反演

• 设 $f(n)$ 为至少满足 $n$ 个条件的方案数，$g(n)$ 为恰好满足 $n$ 个条件的方案数

$$f(i)=\sum_{k=i}^{n}C_{i}^k\times g(k) \leftrightarrow g(i)=\sum _{k=i}^{n}C_{i}^k\times (-1)^{k-i}\times f(k) $$

• 正确显然证明不难留作作业答案略
• 证明过于麻烦，如有兴趣可自行学习

杂题选讲

怎么做题

• 1. 交换求和号
• 2. 合理作差（作商）
  • 前缀和/前缀积
  • 过于简单 不再赘述
• 3. 记忆组合恒等式
• 4. 挖掘题目性质
• 5. __ __ 多 练

NOIP T2

题面

• $n$ 个变量 $x_1, x_2, \ldots , x_n$。每个变量可以取 $1$ 至 $v$ 的整数取值。
• $n - 1$ 条二元限制，其中第 $i$（$1 \leq i \leq n - 1$）条限制为：
  • 若 $x_i = a_i$，则要求 $x_{i+1} = b_i$，且 $a_i$ 与 $b_i$ 为 $1$ 到 $v$ 之间的整数；
  • 当 $x_i \neq a_i$ 时，第 $i$ 条限制对 $x_{i+1}$ 的值不做任何约束。
• $m$ 条一元限制，其中第 $j$（$1 \leq j \leq m$）条限制为：$x_{c_j} = d_j$。
• 一元限制给定，要求构造二元限制，求有解的构造方案数。
• $1 \leq n \leq 10^9$，$1 \leq m \leq 10^5$，$2 \leq v \leq 10^9$

WZH 命题模拟赛 T2

题面

有一棵树，每个点有 $a_i$ 个人。 现在需要设计一个集合点，使所有人都到达该点。 因为会越走越累，所以一个人从点 $u$ 集合至点 $v$ 需要花费 $\text{dis}(u,v)^k$ 的代价。 对于每一个点，求如果选择该点作为集合点，代价的总和。 $n\leq 1e{5},k\leq 10$

CF1536F （div2+div2 F）

题面（略去博弈论部分）

• 圆上 $n$ 个点，每个点最初都空着，开始往圆上放字母（A 或 B）
• 放完之后，相同字母不可相邻，空格不可相邻，A 的数量等于 B 的数量，放到不能再放
• 问不同的放置过程数

ABC266G

题面

求符合要求的字符串个数。 满足要求的字符串 $s$ 具备以下特性：

1. $s$ 由 r、g、b 构成。

2. $s$ 中有 $R$ 个 r，$G$ 个 g，$B$ 个 b，$k$ 个 rg。

sol

• 朴素做法
  • 求出至少有 $i$ 个 rg 的方案数，这个简单插板即可
  • 二项式反演即可
• clever 做法
  • 我们把 rg 看成新的字符，问题转化为：给定四种字符数量，其中两种不能在一起，求方案数，简单插板即可

FD 说批话

题面

• FD 有 $n$ 句批话，它们的长度为 $a_{i}$
• FD 今天要从中选取一些批话来说
• 如果选取的批话中有三句的长度可以构成三角形，则这组批话是有攻击性的
• 一组批话的攻击力定义为：
  • 如果这组批话有攻击性，则攻击性是其中最长的批话的长度 $\times$ 这组批话的个数
  • 否则，这组批话的攻击力为 $0$
• 求在所有可能中，FD 选取的批话的攻击力之和。
• $1\le n\le 5\times 10^3$，$1\le a_i\le 10^9$。

sol

• 容斥，用所有方案的贡献减去没有攻击力的方案的贡献
• 注意到没有攻击性的方案满足 $a[i]+a[i+1]<=a[i+2]$
• 考虑 dp 设 $dp[i][j],f[i][j]$ 分别表示倒数第一个倒数第二个选第 $i,j$ 个数 , 不合法方案中的数的个数和，不合法方案数。
• 注意到可以对 $[i][j]$ 产生贡献的状态是一个范围单调的前缀
• $f[i][j]\leftarrow (pre) f[j][k],dp[i][j]\leftarrow (pre)(dp[j][k]+f[j][k])$
• 考虑如何计算所有方案的价值 : 枚举最大值 , 列出一个形如组合数求和的式子 , 简单推一下 $\rightarrow a[i]\times (i+1)\times 2^{i-2}$

CCPC Online 2024 I

题面

• 在机场，有 $m$ 个人要拿 $n$ 件行李
• 传送带是长条形状的， $n$ 个行李在传送带上的位置分别为 $a_i$，$m$ 个人的位置分别为 $b_i$
• 传送带向坐标轴正方向每秒移动一个单位，即每秒会让所有行李 $a_i \leftarrow a_i + 1$
• 人和行李均从 1 开始编号。显然对于一个人来说，右边的行李都是看过了的，没有自己的行李，自己的行李只可能在其左边，也可能没有。
• 一个人可以至少有零个行李，至多只有一个行李。 一个行李至少属于零个人，至多属于一个人。
• 求在所有情况下，最早有人拿到自己的行李的时刻的和。
• $1 \leq n, m \leq 500,1 \leq a_i \leq 500，1 \leq b_i \leq 500$ 不保证 $a_i,b_{i}$ 之间两两互不相等

sol

• 注意到数据范围很小
• 考虑枚举等待时刻 $t$
• 发现不好做，考虑改变 $t$ 的意义为：至少等待 $t$ 时刻
• 考虑 $O(n^2)$ dp
• 总时间复杂度 $O(n^3)$