（1）从双射法的角度，初步介绍 Catalan 数相关的知识。
（2）复习一下线性筛素数，顺便告知 $\mu$ 的计算方式，现场实现一下。为以后课讲和式变换作铺垫。
（3）二项式定理。上节课提到学校没学过。
（4）顺便讲一些小知识。
普通映射视角下，分类计数可以看成是构造了一个 组合对象 到 类别 的映射。 我们要给一个给定的组合对象，规定它的唯一特征，从而符合映射的要求。
这样，计算组合对象的数量，等价于遍历所有类别， 针对一个特定的类别考虑有多少个组合对象指向它。
双射视角下，两个集合大小相等。 我们需要找到两个集合之间的一一对应。 从而数出一边，就能直接知道另一边。
两种视角可以叠加使用。就像 $a=b$ 和 $b=c$ 能推出 $a=c$ 一样。
有一些小朋友，它们当然有自己的性别。它们各自有一个书包，书包有一种颜色。
第一种思路：我可以考虑 小朋友 到 性别 的映射。 一个小朋友不会有两种性别，所以这的确是一个映射。 我在性别端进行计数。数出每个性别的小朋友的数量，再把这些数量加起来。
第二种思路：小朋友 和 书包 之间是一一对应的关系。它们的总数相同，所以我把书包给数出来即可。
第三种思路：我是不是可以再把两种思路综合一下？ 我再考虑书包的分类计数，按照颜色分类，分别数，加起来，从而数出书包总数。
原理在于，如果一个单射反向连边后仍为映射，或者说有两个方向的单射，即为双射。
实际上，这里暗示了辅助映射的存在性，即书包回到主人的映射。
如果说能找到这样的一个逆映射，实际上就能说明这是一个双射。
下表列出了一些（大小为 $n$ 的结构）组成的集合， 它们的元素个数为第 $n$ 个 Catalan 数 $C_n$：
| 类型 | 示例 | $C_3$ | 特点 |
|---|---|---|---|
| 合法括号序列 | (())() | 5 | 和合法出入栈序列的对应最自然 |
| Dyck 路径 | UUDDUD | 5 | 计数形式最自然 |
| 二叉树 | 见下方 | 5 | 递归形式最自然 |
Dyck 路径的定义，是在长度为 $2n$ 的 UD 序列上：
实际上 Catalan 数还满足如下递归式 $$ C_n = \sum\limits_{i=1}^{n} C_{i-1}\cdot C_{n-i} $$
筛欧拉函数，回忆计算公式。
快速求出 $\varphi(i),i=2,3,4,\cdots,n$。
其实就是要控制，对于一个素因子 $p$，恰好让它乘一次 $\frac{p-1}{p}$。
欧拉筛中，合数 $x$，记它的最小素因子是 $p_{\min}$，$x$ 唯一一次被访问（被筛），是在外层循环访问到 $x/p_{\min}$，内层循环循到 $p_{\min}$（由于最小性，之前不会被 break）。
怎么在之前的基础上，设计算法，快速求出 $\mu(i),i=2,3,4,\cdots,n$。
应用：$n$ 个数，二进制枚举子集的复杂度是 $$ \sum\limits_{i=0}^{n}\binom{n}{i} $$ 怎么计算？
根据NOI活动的发展形势，NOI科学委员会特对NOI系列活动（包括CSP-J/S在内）中编程语言的使用做如下补充说明：
1、除题面有明确要求外，C++程序编译默认采用的语言标准为C++14；
...
在此之前，只有 2011 年发了一个规范，显然没有跟进当年发布的 C++11。
g++，自动编译 + 运行使用 -std=c++XX 参数，例如：
常见版本：
-std=c++11：支持 lambda、auto
-std=c++17：支持结构化绑定-std=c++23：支持 auto 自递归在旧版本中，auto 函数不能递归调用自己
但 C++23 改进了规则，支持如下代码：