入门级-数学-集合和离散化

# 集合
集合是数学中的一个基本概念，用于表示一组明确的、互不相同的元素的全体。以下是一些集合的基本概念和操作：

---

### 基本概念

1. **元素**：集合中的每一个成分被称为元素，可以是数字、字母、点、线等。
2. **空集**：不包含任何元素的集合，用符号 `$ \emptyset $` 或 `{}` 表示。
3. **子集**：如果集合 A 中的每一个元素都是集合 B 的元素，那么 A 是 B 的子集，记作 $$ A \subseteq B $$。
4. **幂集**：一个集合所有子集的集合，包括空集和它自身。

---

5. **并集**：两个或多个集合中所有元素的集合，记作 $$ A \cup B $$。
6. **交集**：两个或多个集合中共有的元素组成的集合，记作 $$ A \cap B $$。
7. **差集**：包含在集合 A 中但不包含在集合 B 中的所有元素组成的集合，记作 $$ A \setminus B $$ 或 $$ A - B $$。
8. **补集**：在全集中去掉集合 A 的所有元素后剩下的元素组成的集合，记作 $$ \complement_{U}A $$ 或 $$ \bar{A} $$（假设全集为 U）。

---

### 表示方法

1. **枚举法**：直接列举集合中的元素，例如 $$ A = \{1, 2, 3\} $$。
2. **描述法**：用一个描述性的条件来表示集合，例如 $$ B = \{x | x \text{ 是一个质数} \} $$。

---

### 运算性质

- **并集** $$ A \cup B $$：元素可以来自 A 或 B 或两者都有。
- **交集** $$ A \cap B $$：元素同时属于 A 和 B。
- **差集** $$ A \setminus B $$：元素属于 A 但不属于 B。
- **补集** $$ \complement_{U}A $$：属于全集 U 但不属于 A 的所有元素。

---

### 特殊集合

- **自然数集**：通常表示为 $$ \mathbb{N} $$，包含所有自然数（1, 2, 3, ...）。
- **整数集**：通常表示为 $$ \mathbb{Z} $$，包含所有整数（..., -3, -2, -1, 0, 1, 2, 3, ...）。
- **有理数集**：通常表示为 $$ \mathbb{Q} $$，包含所有可以表示为两个整数比的数（分数）。
- **实数集**：通常表示为 $$ \mathbb{R} $$，包含所有有理数和无理数。

---

### 例子

假设有两个集合：
- $$ A = \{1, 2, 3\} $$
- $$ B = \{2, 3, 4\} $$

- **并集** $$ A \cup B = \{1, 2, 3, 4\} $$
- **交集** $$ A \cap B = \{2, 3\} $$
- **差集** $$ A \setminus B = \{1\} $$ 和 $$ B \setminus A = \{4\} $$
- **补集** 如果全集是 $$ U = \{1, 2, 3, 4, 5\} $$，那么 $$ \complement_{U}A = \{4, 5\} $$

---

## 二进制集合操作

一个数的二进制表示可以看作是一个集合（$0$ 表示不在集合中，$1$ 表示在集合中）。比如集合 $\{1,3,4,8\}$，可以表示成 $(100011010)_2$。而对应的位运算也就可以看作是对集合进行的操作。

| 操作   |    集合表示     |         位运算语句          |
| ------ | :-------------: | :-------------------------: |
| 交集   |   $a \cap b$    |           `a & b`           |
| 并集   |   $a \cup b$    |   a | b   |
| 补集   |    $\bar{a}$    | `~a` （全集为二进制都是 1） |
| 差集   | $a \setminus b$ |         `a & (~b)`          |
| 对称差 | $a\triangle b$  |           `a ^ b`           |

在进一步介绍集合的子集遍历操作之前，先看位运算的有关应用例子。

---

### 模 2 的幂

一个数对 $2$ 的非负整数次幂取模，等价于取二进制下一个数的后若干位，等价于和 $mod-1$ 进行与操作。

```cpp
// C++ Version
int modPowerOfTwo(int x, int mod) { return x & (mod - 1); }
```

---

于是可以知道，$2$ 的非负整数次幂对它本身取模，结果为 $0$，即如果 $n$ 是 $2$ 的非负整数次幂，$n$ 和 $n-1$ 的与操作结果为 $0$。

事实上，对于一个正整数 $n$，$n-1$ 会将 $n$ 的最低 $1$ 位置零，并将后续位数全部置 $1$。因此，$n$ 和 $n-1$ 的与操作等价于删掉 $n$ 的最低 $1$ 位。

借此可以判断一个数是不是 $2$ 的非负整数次幂。当且仅当 $n$ 的二进制表示只有一个 $1$ 时，$n$ 为 $2$ 的非负整数次幂。

```cpp
// C++ Version
bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
```

---

### 子集遍历

遍历一个二进制数表示的集合的全部子集，等价于枚举二进制数对应掩码的所有子掩码。

掩码是一串二进制码，用于和源码进行与运算，得到屏蔽源码的若干输入位后的新操作数。

掩码对于源码可以起到遮罩的作用，掩码中的 $1$ 位意味着源码的相应位得到保留，掩码中的 $0$ 位意味着源码的相应位进行置 $0$ 操作。将掩码的若干 $1$ 位改为 $0$ 位可以得到掩码的子掩码，掩码本身也是自己的子掩码。

---

给定一个掩码 $m$，希望有效迭代 $m$ 的所有子掩码 $s$，可以考虑基于位运算技巧的实现。

```cpp
// 降序遍历 m 的非空子集
int s = m;
while (s > 0) {
  // s 是 m 的一个非空子集
  s = (s - 1) & m;
}
```

---

或者使用更紧凑的 for 语句：

```cpp
// 降序遍历 m 的非空子集
for (int s = m; s; s = (s - 1) & m)
// s 是 m 的一个非空子集
```

这两段代码都不会处理等于 $0$ 的子掩码，要想处理等于 $0$ 的子掩码可以使用其他办法，例如：

```cpp
// 降序遍历 m 的子集
for (int s = m;; s = (s - 1) & m) {
  // s 是 m 的一个子集
  if (s == 0) break;
}
```

---

接下来证明，上面的代码访问了所有 $m$ 的子掩码，没有重复，并且按降序排列。

假设有一个当前位掩码 $s$，并且想继续访问下一个位掩码。在掩码 $s$ 中减去 $1$，等价于删除掩码 $s$ 中最右边的设置位，并将其右边的所有位变为 $1$。

为了使 $s-1$ 变为新的子掩码，需要删除掩码 $m$ 中未包含的所有额外的 $1$ 位，可以使用位运算 `(s-1) & m` 来进行此移除。

---

这两步操作等价于切割掩码 $s-1$，以确定算术上可以取到的最大值，即按降序排列的 $s$ 之后的下一个子掩码。

因此，该算法按降序生成该掩码的所有子掩码，每次迭代仅执行两个操作。

---

特殊情况是 $s=0$。在执行 $s-1$ 之后得到 $-1$，其中所有位都为 $1$。在 `(s-1)&m` 操作之后将得到新的 $s$ 等于 $m$。因此，如果循环不以 $s=0$ 结束，算法的循环将无法终止。

使用 $\text{popcount}(m)$ 表示 $m$ 二进制中 $1$ 的个数，用这种方法可以在 $O(2^{\text{popcount}(m)})$ 的时间复杂度内遍历集合 $m$ 的子集。

---

### 遍历所有掩码的子掩码

在使用掩码动态编程的问题中，有时会希望对于每个掩码，遍历掩码的所有子掩码：

```cpp
for (int m = 0; m < (1 << n); ++m)
  // 降序遍历 m 的非空子集
  for (int s = m; s; s = (s - 1) & m)
// s 是 m 的一个非空子集
```

这样做可以遍历大小为 $n$ 的集合的每个子集的子集。

---

接下来证明，该操作的时间复杂度为 $O(3^n)$，$n$ 为掩码总共的位数，即集合中元素的总数。

考虑第 $i$ 位，即集合中第 $i$ 个元素，有三种情况：

- 在掩码 $m$ 中为 $0$，因此在子掩码 $s$ 中为 $0$，即元素不在大小子集中。
- 在 $m$ 中为 $1$，但在 $s$ 中为 $0$，即元素只在大子集中，不在小子集中。
- 在 $m$ 和 $s$ 中均为 $1$，即元素同时在大小子集中。

总共有 $n$ 位，因此有 $3^n$ 个不同的组合。

---

还有一种证明方法是：

如果掩码 $m$ 具有 $k$ 个 $1$，那么它有 $2^k$ 个子掩码。对于给定的 $k$，对应有 $C_n^k$ 个掩码 $m$，那么所有掩码的总数为：

$$
\sum_{k=0}^n C_n^k 2^n
$$

上面的和等于使用二项式定理对 $(1+2)^n$ 的展开，因此有 $3^n$ 个不同的组合。

---

# 离散简介

离散化本质上可以看成是一种 [哈希](../string/hash.md)，其保证数据在哈希以后仍然保持原来的全/偏序关系。

---

通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照从大到小编号来处理问题，即离散化。

---

用来离散化的可以是大整数、浮点数、字符串等等。

---

## 实现

C++ 离散化有现成的 STL 算法：

---

### 离散化数组

将一个数组离散化，并进行查询是比较常用的应用场景：

```cpp
// a[i] 为初始数组,下标范围为 [1, n]
// len 为离散化后数组的有效长度
std::sort(a + 1, a + 1 + n);

len = std::unique(a + 1, a + n + 1) - a - 1;
// 离散化整个数组的同时求出离散化后本质不同数的个数。
```

在完成上述离散化之后可以使用 `std::lower_bound` 函数查找离散化之后的排名（即新编号）：

```cpp
std::lower_bound(a + 1, a + len + 1, x) - a;  // 查询 x 离散化后对应的编号
```

---

同样地，我们也可以对 `vector` 进行离散化：

```cpp
// std::vector<int> a, b; // b 是 a 的一个副本
std::sort(a.begin(), a.end());
a.erase(std::unique(a.begin(), a.end()), a.end());
for (int i = 0; i < n; ++i)
  b[i] = std::lower_bound(a.begin(), a.end(), b[i]) - a.begin();
```

---

# 字符串哈希

## 定义

我们定义一个把字符串映射到整数的函数 $f$，这个 $f$ 称为是 Hash 函数。

我们希望这个函数 $f$ 可以方便地帮我们判断两个字符串是否相等。

---

## Hash 的思想

Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。

!!! warning
    这里的「值域较小」在不同情况下意义不同。
    
    在 [哈希表](../ds/hash.md) 中，值域需要小到能够接受线性的空间与时间复杂度。
    
    在字符串哈希中，值域需要小到能够快速比较（$10^9$、$10^{18}$ 都是可以快速比较的）。
    
    同时，为了降低哈希冲突率，值域也不能太小。

---

## 性质

具体来说，哈希函数最重要的性质可以概括为下面两条：

1. 在 Hash 函数值不一样的时候，两个字符串一定不一样；

2. 在 Hash 函数值一样的时候，两个字符串不一定一样（但有大概率一样，且我们当然希望它们总是一样的）。

Hash 函数值一样时原字符串却不一样的现象我们成为哈希碰撞。

---

## 解释

我们需要关注的是什么？

时间复杂度和 Hash 的准确率。

---

通常我们采用的是多项式 Hash 的方法，对于一个长度为 $l$ 的字符串 $s$ 来说，我们可以这样定义多项式 Hash 函数：$f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M$。例如，对于字符串 $xyz$，其哈希函数值为 $xb^2+yb+z$。

特别要说明的是，也有很多人使用的是另一种 Hash 函数的定义，即 $f(s) = \sum_{i=1}^{l} s[i] \times b^{i-1} \pmod M$，这种定义下，同样的字符串 $xyz$ 的哈希值就变为了 $x+yb+zb^2$ 了。

---

显然，上面这两种哈希函数的定义函数都是可行的，但二者在之后会讲到的计算子串哈希值时所用的计算式是不同的，因此千万注意 **不要弄混了这两种不同的 Hash 方式**。

由于前者的 Hash 定义计算更简便、使用人数更多、且可以类比为一个 $b$ 进制数来帮助理解，所以本文下面所将要讨论的都是使用 $f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M$ 来定义的 Hash 函数。

---

下面讲一下如何选择 $M$ 和计算哈希碰撞的概率。

这里 $M$ 需要选择一个素数（至少要比最大的字符要大），$b$ 可以任意选择。

如果我们用未知数 $x$ 替代 $b$，那么 $f(s)$ 实际上是多项式环 $Z_{M}[x]$ 上的一个多项式。考虑两个不同的字符串 $s,t$，有 $f(s)=f(t)$。我们记 $h(x)=f(s)-f(t)=\sum_{i=1}^l(s[i]-t[i])x^{l-i}\pmod M$，其中 $l=\max(|s|,|t|)$。可以发现 $h(x)$ 是一个 $l-1$ 阶的非零多项式。

---

如果 $s$ 与 $t$ 在 $x=b$ 的情况下哈希碰撞，则 $b$ 是 $h(x)$ 的一个根。由于 $h(x)$ 在 $Z_M$ 是一个域（等价于 $M$ 是一个素数，这也是为什么 $M$ 要选择素数的原因）的时候，最多有 $l-1$ 个根，如果我们保证 $b$ 是从 $[0,M)$ 之间均匀随机选取的，那么 $f(s)$ 与 $f(t)$ 碰撞的概率可以估计为 $\frac{l-1}{M}$。简单验算一下，可以发现如果两个字符串长度都是 $1$ 的时候，哈希碰撞的概率为 $\frac{1-1}{M}=0$，此时不可能发生碰撞。

---

## 实现

参考代码：（效率低下的版本，实际使用时一般不会这么写）

```cpp
// C++ Version
using std::string;

const int M = 1e9 + 7;
const int B = 233;

typedef long long ll;

int get_hash(const string& s) {
  int res = 0;
  for (int i = 0; i < s.size(); ++i) {
    res = (ll)(res * B + s[i]) % M;
  }
  return res;
}

bool cmp(const string& s, const string& t) {
  return get_hash(s) == get_hash(t);
}
```

---

## Hash 的分析与改进

---

### 错误率

若进行 $n$ 次比较，每次错误率 $\dfrac 1 M$，那么总错误率是 $1-\left(1-\dfrac 1 M\right)^n$。在随机数据下，若 $M=10^9 + 7$，$n=10^6$，错误率约为 $\dfrac 1{1000}$，并不是能够完全忽略不计的。

所以，进行字符串哈希时，经常会对两个大质数分别取模，这样的话哈希函数的值域就能扩大到两者之积，错误率就非常小了。

---

### 多次询问子串哈希

单次计算一个字符串的哈希值复杂度是 $O(n)$，其中 $n$ 为串长，与暴力匹配没有区别，如果需要多次询问一个字符串的子串的哈希值，每次重新计算效率非常低下。

---

一般采取的方法是对整个字符串先预处理出每个前缀的哈希值，将哈希值看成一个 $b$ 进制的数对 $M$ 取模的结果，这样的话每次就能快速求出子串的哈希了：

令 $f_i(s)$ 表示 $f(s[1..i])$，即原串长度为 $i$ 的前缀的哈希值，那么按照定义有 $f_i(s)=s[1]\cdot b^{i-1}+s[2]\cdot b^{i-2}+...+s[i-1]\cdot b+s[i]$

---

现在，我们想要用类似前缀和的方式快速求出 $f(s[l..r])$，按照定义有字符串 $s[l..r]$ 的哈希值为 $f(s[l..r])=s[l]\cdot b^{r-l}+s[l+1]\cdot b^{r-l-1}+...+s[r-1]\cdot b+s[r]$

对比观察上述两个式子，我们发现 $f(s[l..r])=f_r(s)-f_{l-1}(s) \times b^{r-l+1}$ 成立（可以手动代入验证一下），因此我们用这个式子就可以快速得到子串的哈希值。其中 $b^{r-l+1}$ 可以 $O(n)$ 的预处理出来然后 $O(1)$ 的回答每次询问（当然也可以快速幂 $O(\log n)$ 的回答每次询问）。

---

## Hash 的应用

---

### 字符串匹配

求出模式串的哈希值后，求出文本串每个长度为模式串长度的子串的哈希值，分别与模式串的哈希值比较即可。

### 允许 $k$ 次失配的字符串匹配

问题：给定长为 $n$ 的源串 $s$，以及长度为 $m$ 的模式串 $p$，要求查找源串中有多少子串与模式串匹配。$s'$ 与 $s$ 匹配，当且仅当 $s'$ 与 $s$ 长度相同，且最多有 $k$ 个位置字符不同。其中 $1\leq n,m\leq 10^6$，$0\leq k\leq 5$。

---

这道题无法使用 KMP 解决，但是可以通过哈希 + 二分来解决。

枚举所有可能匹配的子串，假设现在枚举的子串为 $s'$，通过哈希 + 二分可以快速找到 $s'$ 与 $p$ 第一个不同的位置。之后将 $s'$ 与 $p$ 在这个失配位置及之前的部分删除掉，继续查找下一个失配位置。这样的过程最多发生 $k$ 次。

总的时间复杂度为 $O(m+kn\log_2m)$。

---

### 最长回文子串

二分答案，判断是否可行时枚举回文中心（对称轴），哈希判断两侧是否相等。需要分别预处理正着和倒着的哈希值。时间复杂度 $O(n\log n)$。

这个问题可以使用 manacher 算法 在 $O(n)$ 的时间内解决。

---

通过哈希同样可以 $O(n)$ 解决这个问题，具体方法就是记 $R_i$ 表示以 $i$ 作为结尾的最长回文的长度，那么答案就是 $\max_{i=1}^nR_i$。考虑到 $R_i\leq R_{i-1}+2$，因此我们只需要暴力从 $R_{i-1}+2$ 开始递减，直到找到第一个回文即可。记变量 $z$ 表示当前枚举的 $R_i$，初始时为 $0$，则 $z$ 在每次 $i$ 增大的时候都会增大 $2$，之后每次暴力循环都会减少 $1$，故暴力循环最多发生 $2n$ 次，总的时间复杂度为 $O(n)$。

---

### 最长公共子字符串

问题：给定 $m$ 个总长不超过 $n$ 的非空字符串，查找所有字符串的最长公共子字符串，如果有多个，任意输出其中一个。其中 $1\leq m, n\leq 10^6$。

很显然如果存在长度为 $k$ 的最长公共子字符串，那么 $k-1$ 的公共子字符串也必定存在。因此我们可以二分最长公共子字符串的长度。假设现在的长度为 $k$，`check(k)` 的逻辑为我们将所有所有字符串的长度为 $k$ 的子串分别进行哈希，将哈希值放入 $n$ 个哈希表中存储。之后求交集即可。

时间复杂度为 $O(n\log_2\frac{n}{m})$。

---

### 确定字符串中不同子字符串的数量

问题：给定长为 $n$ 的字符串，仅由小写英文字母组成，查找该字符串中不同子串的数量。

为了解决这个问题，我们遍历了所有长度为 $l=1,\cdots ,n$ 的子串。对于每个长度为 $l$，我们将其 Hash 值乘以相同的 $b$ 的幂次方，并存入一个数组中。数组中不同元素的数量等于字符串中长度不同的子串的数量，并此数字将添加到最终答案中。

---

为了方便起见，我们将使用 $h [i]$ 作为 Hash 的前缀字符，并定义 $h[0]=0$。

"参考代码"
```cpp
    int count_unique_substrings(string const& s) {
      int n = s.size();
    
      const int b = 31;
      const int m = 1e9 + 9;
      vector<long long> b_pow(n);
      b_pow[0] = 1;
      for (int i = 1; i < n; i++) b_pow[i] = (b_pow[i - 1] * b) % m;
    
      vector<long long> h(n + 1, 0);
      for (int i = 0; i < n; i++)
        h[i + 1] = (h[i] + (s[i] - 'a' + 1) * b_pow[i]) % m;
    
      int cnt = 0;
      for (int l = 1; l <= n; l++) {
        set<long long> hs;
        for (int i = 0; i <= n - l; i++) {
          long long cur_h = (h[i + l] + m - h[i]) % m;
          cur_h = (cur_h * b_pow[n - i - 1]) % m;
          hs.insert(cur_h);
        }
        cnt += hs.size();
      }
      return cnt;
    }
```

---

### 例题

"[CF1200E Compress Words](http://codeforces.com/contest/1200/problem/E)"
给你若干个字符串，答案串初始为空。第 $i$ 步将第 $i$ 个字符串加到答案串的后面，但是尽量地去掉重复部分（即去掉一个最长的、是原答案串的后缀、也是第 $i$ 个串的前缀的字符串），求最后得到的字符串。
    
字符串个数不超过 $10^5$，总长不超过 $10^6$。

---

"题解"
每次需要求最长的、是原答案串的后缀、也是第 $i$ 个串的前缀的字符串。枚举这个串的长度，哈希比较即可。
        
当然，这道题也可以使用 [KMP 算法](./kmp.md) 解决。