附中讲课：从离散数学的观点看OI

布尔代数简介

化简：((a && b) || (c %% !b)) && (!a || b || c)

布尔代数：以bool值为基本研究对象。以1表示真，0表示伪。

用*来表示逻辑与，用+来表示逻辑或。

则有基本的运算规律：

A	B	A+B	A*B
0	0	0	0
0	1	1	0
1	0	1	0
1	1	1	1

另外，引入“非”运算：$\overline A$为$A$的取反。

艾弗森括号：$[p]=\begin{cases}1,& 命题p成立 \\ 0,& 命题p不成立\end{cases}$ e.g. [1==2]为0；[3|x]在$x$取3的倍数时为1，否则为0。

这个记号方便了我们表达一些实际问题。例如，假设我们手中有一张表$\varphi(n)$，要求出互质的$(i,j)$的对数。答案就是：

$$\sum_i\sum_j [i\perp j] = \sum_i\sum_j[i\perp j] = 2\sum_i\sum_j^i[i\perp j]-1=2\sum_i\varphi(i)-1$$

如果要求出所有数对$(i,j)$的gcd之和，怎么搞？

$$ans = \sum_i\sum_j \gcd(i,j)$$
枚举$\gcd(i,j)=d$.考虑到每一个$d$对答案作出了$\sum_i\sum_j[\gcd(i,j)==d]$次贡献，故
$$ans = \sum_d d *\sum_i\sum_j[\gcd(i,j)==d]$$
$[\gcd(i,j)==d]$，必然$d$同时是$i,j$的因数。满足这个条件的$(i,j)$有多少对呢？它们分别可以取遍$d$的所有倍数，也就是$0,d,2d,3d....$亦即
$$ans = \sum_d d*\sum_{p=1}^{\lfloor n/d \rfloor}\sum_{q=1}^{\lfloor n/d \rfloor}[\gcd(pd,qd)==d] \\ = \sum_d d*\sum_{p=1}^{\lfloor n/d \rfloor}\sum_{q=1}^{\lfloor n/d \rfloor}[\gcd(p,q)==1]$$

后面的柿子我们已经会求了，故可以$O(n)$做完此题。

实际上，存在$O(\sqrt{n})$应对每次查询的办法。（数论分块）

以上练习了艾弗森括号的使用。它将在我们做数论题的时候发挥重大作用。

回来继续讨论布尔代数。首先，不难发现结合律、交换律、分配律。
有几个恒等式：$A+\overline A=1$，$A*\overline A=0$。$1+A=1$，$0*A=0$.

依据这些法则，我们能否化简$A+AB$呢？$A+AB = A(1+B) = A*1 = A$
人话：假设$A=1$，那么$A+AB=1+x=1$；否则$ans=0+0*x=0$，故$ans=A$.

$A+\overline A B = ?$

De Morgan定理

位运算简介

众所周知，C++支持一些位运算，下面以int型为例。每个int变量可以视为长度为32的布尔数组，& | ^都是逐位运算。

如果要判断一个数是奇数还是偶数，怎么做？
如果要判断一个数是不是8的倍数，怎么做？
补码是什么？

如何取出一个数的二进制上的 最后一个 1？例如，10001111100取出00000000100

今有一个长度为$2n+1$的数组，已知这里面：$n$个数重复出现了两次；只有一个数仅出现一次。要求快速找到这个仅出现一次的数。

集合论初步

我们把一些“东西”叫做集合。
集合元素必须要是确定的、可以互相区别开的事物。

下面哪个属于集合？
A. 上海交通大学的“好几百个”教授
B. 所有跑得快的记者
C. 身高不低于1.80m的拥有美国国籍的人

空集

属于、包含于
交集、并集、补集、差集

集合论上的De Morgan定理
对称差运算

集合论不仅能描述事物，还可以描述事物之间的联系。

公理1. 人都是要死的。
公理2. 苏格拉底是人。
结论. 苏格拉底biss。

我们用集合论的语言重新描述这个推理过程。
公理1. 凡是人都得死，故“human”这一集合包含于“biss”集合。
公理2. 苏格拉底是人，故“Socrates”这一元素属于“human”集合。
结论. “Socrates”属于“biss”集合。苏格拉底biss。

刚刚我们由“凡是人都得死”，得到了$human \subset biss$。从这里我们可以导出“子集”的定义：$A$是$B$的子集，当且仅当

$$\forall x\in A,x\in B$$
也可以导出另一个等价定义：
$$\forall x\not\in B,x\not \in A$$

它们的等价性取决于这样一个事实：命题p与其逆否命题，正确性一致。

幂集：考虑一个新的集合：它的每个元素都是$A$的子集。这样的集合$S$记为$2^A$.
$S$有多少个元素？
若$A={1,2,3}$，那么$2^A=?$
若$A={1}$，那么$2^{2^A}=?$

抽屉原理：（又称鸽巢原理）把$n+1$个苹果放进$n$个箱子，必然存在一个箱子，里面放了至少两个苹果。
【推广】平均值原理：把$np+1$个苹果放进$n$个箱子，必然存在一个箱子，里面放了至少$p+1$个苹果。

求证：任意取52个正整数，这里面必然存在$(i,j)$，使得要么$i+j$是100的倍数，要么$i-j$是100的倍数。

// 求证：在$1,2...2n$中任取$n+1$个数，必然有一个数是另一个数的倍数。

容斥原理

关系

首先来研究笛卡尔积。

称$A\times A$的子集R为定义在A上的关系。若$(x,y)\in R$，则称$xRy$。
例如，整除关系。$A={1,2,3}$，则整除关系为$\{(1,1),(1,2),(1,3),(2,2),(3,3)\}$

一个关系R肯定可以被记录在矩阵中（称为关系矩阵）。

• 自反性 $xRx$始终成立。
• 反自反性 $xRx$始终不成立。
• 对称性 若$xRy$则$yRx$。
• 反对称性 若$xRy(x\neq y)$，则$y\not Rx$
• 传递性 若$xRy,yRz$，则$xRz$.

今有n个点，某些点之间修了路，问每个点最终能到达哪些点。（传递闭包）

几类特殊的关系：

• 等价关系 自反，对称，传递
• 偏序关系 自反，反对称，传递
• 全序关系 反对称，传递，完全

等价关系和等价类

偏序关系可以映射到DAG上去。这就是“Hasse图”。

什么东西可以用线段树维护？

利用每个节点记录的信息，可以得知这一区间的答案；可以很方便地合并两个相邻区间的答案。
max值/sum值明显可以。
今有任务：实时查询区间最小值和最小值出现的次数。能否直接用线段树维护？

ST表：必须满足区间可加性。

映射

映射$f:X\to Y$是$X\times Y$的一个子集，且满足：

• $\forall x\in X$，有一个$f(x)\in Y$与之对应。（定义域的遍历性）
• 对于每个$x$，只会被映射到唯一的$y$。即单值性：$f(x)$的值唯一确定。

单射、满射、双射

群论的概念

封闭性
结合律
单位元
逆元

则称为一个群。
(有理数,乘法)：群。(无理数，乘法)：不是群。
(整数，乘法)：不是群。(正整数，乘法)：是群。

能用树状数组维护，必然满足性质：$F(l,r)=F(1,r)-F(1,l-1)$
此时出现了减号，要求存在逆元。

图论