简介

Min_25筛用来求一个函数的前缀和

如果函数是积性函数就可以做，如果不是积性函数的话有一部分也是可以做的

算法过程就像是在模拟埃氏筛法

时间复杂度是$O(\frac{n^{\frac{3}{4}}}{log(\sqrt{n})})$，然而我并不会证

概念

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$

表达式

容斥原理

$$ | 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| $$