概念

1. 样本空间：一个随机试验的所有可能结果组成的集合，标记为$S$

2. 事件：$S$的一个子集$A$，$A\subseteq \Omega$，称为事件

简介

设数集$T$，$T$的线性基为最小的一个集合$S$，$S$与$T$通过异或运算能产生的集合相同，也就是$S$是$T$的线性无关极大子集

性质

1. 线性基的异或集合中每个元素的异或方案唯一
2. 线性基二进制最高位互不相同

证明的方法

用来证明形如$\forall x(P(x)\to Q(x))$的定理

直接证明法

也就是条件语句$p\to q$

反证法

条件语句$p\to q$等价于它的逆否命题$\neg q \to \neg p$

Prufer序

一个Prufer数列和一个带编号的无根树是一一对应的

树->Prufer序

每次找这棵树中编号最小的叶子节点，将与这个点相连的点加入Prufer序，去掉这个点以及相连的边。重复这个操作直到剩下两个点。

Prufer序->树

设点集$ V={1,2,…,n} $，每次在$V$中找出最小的未在Prufer序中出现过的数，然后在$V$中删除，与Prufer序中的第一个数相连，Prufer序中的第一个数删除。重复这个操作直到$|V|=2$（Prufer序为空），最后将$V$中的两个点相连。

表达式

容斥原理

$$ | A_1 \cup A_2 \cup \cdots \cup A_n | = \sum^n_{i=1}|A_i|- \sum_{1 \leq i < j \leq n}|A_i \cap A_j|+\ \sum_{1 \leq i < j < k \leq n}|A_i \cap A_j \cap A_k| - \cdots +(-1)^{n-1}|A_1 \cap A_2 \cap \cdots \cap A_n| $$

dsu on tree

可以用来解决一些有下列性质的问题：

1. 对子树询问
2. 没有修改

算法

算法步骤如下：

• 遍历的一个节点
  • 递归所有的轻儿子
  • 递归重儿子
  • 统计轻儿子对答案的影响
  • 计算答案
  • 如果自己是轻儿子，消除影响