《浅谈信息学竞赛中数据的构造与生成》阅读笔记
a1co0av5ce5az1cz0ap_
·
·
算法·理论
from 刘一平 2023 年的论文
前言
在测试自己程序的正确性时，常用的方法有自己构造小数据和直接对拍。而在对拍或者为题目造数据的时候，数据的强度会成为一个很大的问题，强度不够可能会导致无法查出自己代码的错误或者让一些复杂度错误的代码通过较大的数据。
本文介绍了几种常见的数据生成方式以及如何生成出更加随机或更加具有针对性的数据。
序列
排列
随机排列的方式一般有两种，它们看起来比较相似，但是原理不同。
第一种算法如下：
\begin{array}{l}\hline
\textbf{算法 1 }随机排列\\\hline
\textbf{输入：}n\\
\textbf{输出：}一个 1 到 n 的随机排列\\\hline
\begin{array}{rl}
1&\text{let }p_i=i\\
2&\textbf{for }i=1\to n\textbf{ do}\\
3&\quad j\gets\text{random}(1,i)\\
4&\quad \text{swap}(p_i,p_j)\\
5&\textbf{done}\\
6&\textbf{return }p
\end{array}\\\hline
\end{array}
其中 \text{random}(l,r) 表示等概率随机一个 [l,r] 之间的整数。
引理 1.1.1. 算法 1 可以等概率随机生成一个 1\sim n 的排列。
证明：这个打乱算法是先对 p 的前 n-1 项进行规模为 n-1 的打乱，然后令 j=\text{random}(1,n)，并交换 p_n 与 p_j，于是考虑对 n 归纳。
命题对于 n=1 显然成立，考虑由 n-1 成立推出 n 成立。交换后有 p_j=n，因为 j 是等概率随机的，所以只需要证明 p_1\sim p_{j-1},p_{j+1}\sim p_n 是等概率随机的排列即可。而这与交换前的 p_1\sim p_{n-1} 构成双射，所以交换后的是一个等概率随机的排列。\square
第二种算法如下：
\begin{array}{l}\hline
\textbf{算法 2 }随机排列\\\hline
\textbf{输入：}n\\
\textbf{输出：}一个 1 到 n 的随机排列\\\hline
\begin{array}{rl}
1&\text{let }p_i=i\\
2&\textbf{for }i=1\to n\textbf{ do}\\
3&\quad j\gets\text{random}(i,n)\\
4&\quad \text{swap}(p_i,p_j)\\
5&\textbf{done}\\
6&\textbf{return }p
\end{array}\\\hline
\end{array}
引理 1.1.2. 算法 2 可以等概率随机生成一个 1\sim n 的排列。
证明：这个算法可以看作先把 p_1 交换为 1\sim n 的值之一，然后对 p_2\sim p_n 做规模为 n-1 的算法。与上面类似的方法对 n 归纳证明即可。\square
无重复元素的序列
你需要等概率随机一个长为 n 的序列，值域为 1 到 m（m\ge n）的整数且序列中的元素不重复。
一种方法如下：
\begin{array}{l}\hline
\textbf{算法 3 }随机无重复元素的序列\\\hline
\textbf{输入：}n\\
\textbf{输出：}一个长为 n 的无重复元素的序列\\\hline
\begin{array}{rl}
1&\text{let }a_i=0\\
2&\textbf{for }i=1\to n\textbf{ do}\\
3&\quad a_i\gets\text{random}(1,m)\\
4&\quad\textbf{while }a_i\in\{a_1,a_2,\dots,a_{i-1}\}\textbf{ do}\\
5&\quad\quad a_i\gets\text{random}(1,m)\\
6&\quad\textbf{done}\\
7&\textbf{done}\\
8&\textbf{return }p
\end{array}\\\hline
\end{array}
引理 1.2.1. 算法 3 可以等概率随机生成一个长度为 n，值域为 [1,m]\cap\mathbb Z 且元素不重复的序列。
这种方法的弊端是在 m 较小的时候生成会比较慢。例如 m=n 时，调用 \text{random} 的期望次数为 \sum\limits_{i=1}^n\dfrac ni=\Theta(n\log n)。
判断 a_i\in\{a_1,a_2,\dots,a_{i-1}\} 可以用哈希表做到 \Theta(1)，总复杂度为 \Theta(n\log n)。
不过在 m 较小时可以生成一个 1\sim m 的随机排列然后取前 n 项。
在 m\le 2n 时采用第二种算法，这部分复杂度为 \Theta(n)。而在 m>2n 时仍采用第一种算法，每次随机到之前没出现过的值的概率为 \dfrac{m-i+1}m\ge\dfrac 12，期望复杂度 \Theta(n)。
另一种方法是使用算法 2，只需要将 i 循环到 n，用哈希表存储被操作过的位置以及它们的值，就可以做到 \Theta(n)。
和固定的序列
你现在需要等概率随机一个长为 n 的正整数序列 a_1\sim a_n，要求 \sum\limits_{i=1}^na_i=m。
设 s_i=\sum\limits_{j=1}^ia_j，考虑生成 s。因为 1\le s_1<s_2<\dots<s_n=m 的 s 与 a 一一对应，因此等概率随机一个 a 与等概率随机一个 s 等价。
而生成这样的 s 等价于在 1\sim m-1 中等概率随机选择 n-1 个不同正整数，问题转化为了生成无重复元素序列的问题。
如果要求 a_i 的下界为 b_i，可以将 a 减去 (b_i-1) 转化为下界为 1 的情况。
图
树
方法 1：随机父亲
一种常见的随机生成树的方法如下：\forall 2\le i\le n，在 1\sim i-1 中等概率随机一个点作为 i 的父亲。
对于一棵有根树，定义其点的深度为其到根节点的最短路径上的边数，定义这棵树的高度是所有点深度的最大值。
引理 2.1.1. \forall 2\le i\le n，在 1\sim i-1 中等概率随机选择一个点作为 i 的父亲，这样生成是树高期望是 \Theta(\log n)。
引理 2.1.2（琴生不等式）. 对于函数 f 在区间 [L,R] 内下凸，对于任意实数 x_1,x_2,\dots,x_n\in[L,R] 以及 a_1,a_2,\dots,a_n 满足 \sum\limits_i a_i=1 且 a_i>0，则有 f(\sum a_ix_i)\le\sum a_if(x_i)。
引理 2.1.2 的证明略。
引理 2.1.1 的证明：设树高为 h，根据琴生不等式，有 2^{E[h]}\le E[2^h]，考虑计算 E[2^h] 的上界。
设点 i 深度为 d_i，那么 E[2^h]=E\left[\max\limits_{i=1}^n(2^{d_i})\right]\le E\left[\sum\limits_{i=1}^n 2^{d_i}\right]=\sum\limits_{i=1}^n E[2^{d_i}]。
设 f_i=E[2^{d_i}]，那么 f_1=1，而 \forall 2\le i\le n 有 f_i=\dfrac 2{i-1}\sum\limits_{j=1}^{i-1}f_j。
设 F_i=\sum\limits_{j=1}^i f_j，那么就有 F_i-F_{i-1}=\dfrac 2{i-1}F_{i-1}。那么
\begin{aligned}F_i&=\dfrac{i+1}{i-1}F_{i-1}\\&=\prod\limits_{j=2}^i\dfrac{j+1}{j-1}\\&=\dfrac{(i+1)i}2\end{aligned}
所以 2^{E[h]}\le E[2^h]\le F_n=\dfrac{(n+1)n}2，两边取对数得 E[h]=O(\log n)。
从另一个方向，E[h]\ge E\left[\dfrac 1n\sum\limits_{i=1}^nd_i\right]=\dfrac 1n\sum\limits_{i=1}^n E[d_i]。
设 g_i=E[d_i]，那么 g_1=0，\forall 2\le i\le n,g_i=1+\dfrac 1{i-1}\sum\limits_{j=1}^{i-1}g_j。
设 G_i=\sum\limits_{j=1}^i g_j，\forall 2\le i\le n,G_i-G_{i-1}=1+\dfrac 1{i-1}G_{i-1}，因此
\begin{aligned}G_i&=1+\dfrac i{i-1}G_{i-1}\\&=\sum\limits_{j=2}^i\prod\limits_{k=j}^{i-1}\dfrac{k+1}k\\&=\sum\limits_{j=2}^i\dfrac ij\\&=\Theta(i\log i)\end{aligned}
所以 E[h]\ge\dfrac 1n\sum\limits_{i=1}^n E[d_i]=\dfrac 1nG_n\Theta(\log n)，所以 E[h]=\Omega(\log n)。
综上，E[h]=\Theta(\log n)。\square
树高期望为 \Theta(\log n) 很多时候并不能很好的测试算法效率。例如一些算法的复杂度为 \Theta(\sum sz_i)=\Theta(\sum dep_i)，其中 sz_i 和 dep_i 分别表示点 i 的子树大小以及深度，这种数据下期望复杂度为 \Theta(n\log n)，而实际最高复杂度为 \Theta(n^2)。
如果启发式合并时没有选择最大的儿子作为重儿子或者链修改时出现错误，都有可能导致算法出现这个复杂度，而无法在这种数据下发现问题。
方法 2：在一定范围内随机父亲
修改方法 1 的常见方法是在限定范围内随机父亲。
我们可以设定一个阈值 B，点 i 的父亲在 [\max(1,i-B),i-1] 内随机。
使用这种方法通常需要适时调整 B 的大小以生成不同类型的数据。一般会将 B 设得比较小，例如 n=2\times 10^5 的数据可以设定 B=10 或 20，这样生成的树比较适合测试启发式合并。
方法 3：Prufer 序列
对于一棵有标号无根树，它的 Prufer 序列由如下方法生成：
\begin{array}{l}\hline
\textbf{算法 4 }\text{Prufer }序列\\\hline
\textbf{输入：}一棵 n 个点的有标号无根树 T\\
\textbf{输出：}T 的\text{ Prufer }序列\\\hline
\begin{array}{rl}
1&\text{let }a_i=0\\
2&\textbf{for }i=1\to n-2\textbf{ do}\\
3&\quad u\gets\text{编号最小的叶子}\\
4&\quad a_i\gets\text{与 $u$ 相邻的点的标号}\\
5&\quad \text{删除 u 以及它的邻边}\\
6&\textbf{done}\\
7&\textbf{return }a
\end{array}\\\hline
\end{array}
可以看出一个 n 个点的有标号无根树的 Prufer 序列是一个长度为 n-2，值域为 [1,n]\cap\mathbb Z 的序列。
一棵树唯一对应了一个 Prufer 序列，而且一个合法序列对应了一棵树：
引理 2.1.3. Prufer 序列构建了一个从 n 个点的数到度为 n-2，值域为 [1,n]\cap\mathbb Z 的序列的双射。
证明：只需要证明每个 Prufer 序列都存在唯一的树 T 与之对应。
考虑对 n 归纳。n=2 的证明是简单的，考虑用 n-1 推出 n。设给定的 Prufer 序列为 a_1\sim a_{n-2}，不难发现一个点在 Prufer 序列中的出现次数为其度数减 1，于是可以确定所有叶子，设最小的叶子为 u，与 u 相邻的点为 a_1。
考虑 Prufer 序列 a_2,\dots,a_{n-2}，标号集合为 \{1,\dots,n\}\backslash\{u\}。根据归纳假设，此时存在唯一的树 T' 与其对应。在 T' 中加入 u 并与 a_1 连边得到树 T，显然这时唯一的与 a 对应的树。\square
以上的证明同时给出了一个由 Prufer 序列构造对应树的方法，即从后向前构造，每次添加一个叶子。
如果要从所有有标号无根树中等概率随机一个，只需要随机它的 Prufer 序列即可，这种生成方式还可以固定每个点的度数。
方法 4：链
### 方法 5：完全二叉树
$\forall 2\le i\le n$ 选取 $\lfloor\dfrac i2\rfloor$ 作为 $i$ 的父亲即可得到一棵完全二叉树。
这样生成的树进行树链剖分后所有点的轻儿子大小之和为 $\Theta(n\log n)$ 级别。
### 方法 6：结合链与完全二叉树
取两个阈值 $B_1,B_2$，取前 $B_1$ 个点构造完全二叉树，后面每 $B_2$ 个点连成一条链连接在前 $B_1$ 个点上，一般 $B_1$ 和 $B_2$ 都会选取在 $\Theta(\sqrt n)$ 级别，一种常见的取值方式是取 $B_1=\lfloor 2\sqrt n\rfloor,B_2=\lfloor\sqrt n\rfloor$，在下面的小节中我们也将这样取值。
这样生成的数据既有比较长的链，所有点的轻儿子大小之和又为 $\Theta(n\log n)$。
### 对比
接下来对比上述生成方法。我们先生成一棵大小为 $n$ 的树，钦定点 1 为根，然后将每个点的邻边随机打乱，进行 dfs，最后进行 $Q$ 次查询，每次随机两个点查询路径信息。
上述过程会进行 $T$ 次，测得以下数值取 $T$ 次平均值：
- $S_{size}$ 表示所有点子树大小之和，部分高复杂度算法依赖于此。
- $S_{son}$ 表示轻重链剖分后所有点轻子树大小之和，可以用来评估启发式合并效率。
- $S_{random}$ 表示每个点随机选择一个点作为重儿子后所有点的轻子树大小之和，可以用来评估错误的启发式合并方法的效率。
- $S_{len}$ 表示 $Q$ 次查询的路径长度平均值。部分高复杂度算法依赖于此，也可以用于评估链上数据结构的效率。
- $S_{jump}$ 表示轻重链剖分后 $Q$ 次查询路径上的轻边个数的平均值，可以用来评估树链剖分的效率。
取 $n=10^5,Q=10^5,T=10^3$，测量结果如下（保留三位小数）：
可以看到：
- 方法 1：优点是代码简短，$S_{son}$ 较大，缺点是 $S_{random},S_{len},S_{jump}$ 都过小，难以测试例如启发式合并和树链剖分的复杂度问题。
- 方法 2：$S_{size},S_{random},S_{len}$ 较大，并且随着 $B$ 减小有增加趋势。
- 方法 3：在测试的数据类型中各项数值大小较为居中。
- 方法 4：$S_{size},S_{len}$ 明显较大，链比较适用于测试链上数据结构在极限大小下的效率。
- 方法 5：$S_{son},S_{jump}$ 较大，比较适用于测试启发式合并、树链剖分的效率。
- 方法 6：强度介于方法 4 和方法 5 之间。
## 任意图
生成 $n$ 个点 $m$ 条边的无重边无自环的无向图，就是要在 $\binom n2$ 条边中选择 $m$ 条，使用之前序列的技巧即可。如果要生成连通图，可以不断生成直到其连通。
## 仙人掌
仙人掌就是每条边至多在一个简单环中的图。本文认为仙人掌可以有重边但不能有自环。
感性理解，仙人掌就是若干个环串成了一棵树的形状。树也是一种仙人掌，所以仙人掌常常被作为树的扩展。下面介绍几种随机仙人掌的方法。
### 方法 1
考虑仙人掌的圆方树（即对于每个环建立一个方点连接所有环上的点），其有如下性质：
- 每条边连接一个圆点和一个方点。
- 所有度数 $\le 1$ 的点是圆点。
如果要随机一个仙人掌，我们可以先随机一棵树将其黑白染色作为它的圆方树。
如果要生成的圆方树点数为 $n$，那么我们可以先随机一棵点数为 $2n$ 的树，黑白染色后取数量较少的颜色为圆点，那么圆点个数一定不超过 $n$。
因为圆方树的叶子必须是圆点，我们需要将所有作为叶子的方点删除。
### 方法 2
先随机一棵树，然后在这棵树上加一些边，使其成为仙人掌。
对这棵树 dfs，回溯时以一定概率向一个随机祖先连边，并将这条路径上的边打标记，表示它们已经在一个环上了。问题是如何确定这个概率以及连边的祖先。我们可以设定一个阈值 $P$。在点 $u$ 处回溯时，可以用如下方法确定向祖先的连边：
$$
\begin{array}{l}\hline
\textbf{算法 5 }连边\\\hline
\begin{array}{rl}
1&v\gets u\\
2&\textbf{while }v 不为根且 v 的父边未标记\textbf{ do}\\
3&\quad x\gets\text{randomrealnumber}(0,1)\\
4&\quad\textbf{if }x<P\textbf{ then}\\
5&\quad\quad v\gets fa_v\\
6&\quad\textbf{else break}\\
7&\quad\textbf{end if}\\
8&\textbf{done}\\
9&\textbf{if }u\neq v\textbf{ then}\\
10&\quad 连边 (u,v)\\
11&\quad 将 u 到 v 的路径打上标记\\
12&\textbf{end if}
\end{array}\\\hline
\end{array}
$$
例如取 $P=0.1$，生成出的环会比较小。
### 方法 3
依然考虑先随机一棵树然后加边的方式。取一个参数 $K$，随机 $K$ 次，每次随机两个点 $u,v$ 判断是否可以在 $u,v$ 间连一条边，如果可以就连。
判断方法与方法 2 类似，每条树边上打标记表示这条边是否已经在环上。判断时只需要检查 $u\to v$ 的路径上是否有带标记的边。
如果要保证生成大规模数据的时间复杂度，需要数据结构维护标记。实际上沿路径逐步判断，遇到标记就退出，其效率也较高。
### 对比
测试 $T$ 次，每次随机一个仙人掌，然后测得以下数值，$T$ 次取平均值：
- 节点个数 $N$；
- 环的个数 $C$；
- 环长平均值 $\bar L$；
- 环长方差 $\sigma$；
- 环长最大值 $M$。
取 $n=10^5,T=10^3$，生成树的方法为随机 Prufer 序列，测量结果如下：
可以看到：
- 方法 1：可以通过每个点的度数控制环长的分布，但会略微减小 $N$，在均匀随机 Prufer 序列时环长较短但个数较多，方差较小。
- 方法 2：可以通过调节 $P$ 来调节环长，$P$ 增加时，$C,\bar L,\sigma,M$ 都有增加趋势。总体上环长较短，环的个数较多，方差较小。
- 方法 3：特点是环的个数较少，环长较长，方差较大。
# 括号串
括号串是由 `(` 和 `)` 两种字符组成的字符串。
对于一个括号串 $s=s_1s_2\dots s_n$，定义它的路径序列 $a_0\sim a_n$ 如下：
$$a_i=\begin{cases}0&i=0\\a_{i-1}+1&i>0,s_i=(\\a_{i-1}-1&i>0,s_i=)\end{cases}$$
定义 $s$ 是平衡的，当且仅当 $a_n=0$。
定义 $s$ 的缺陷度 $defect(s)$ 为满足 $\min(a_i,a_{i+1})<0$ 的 $i$ 的个数除以 2 的结果（显然其个数总是偶数）。
定义 $s$ 合法当且仅当 $s$ 平衡且 $s$ 缺陷度为 $0$。
定义 $D_{n,k}$ 为长度为 $n$ 且缺陷度为 $k$ 的平衡括号串集合。
定义 $s^R$ 表示 $s$ 反转后的串。
对于偶数 $n$，$D_{n,0}$ 就表示长度为 $n$ 的合法括号串集合，$|D_{n,0}|=\dfrac 1{n/2+1}\dbinom n{n/2}$。
对于一个平衡括号串 $s$，定义一种变换 $\Phi(s)$ 如下：
- 如果 $s$ 为空，那么 $\Phi(s)$ 为空串。
- 如果 $s$ 非空，那么将其分解为 $s=lr$ 的形式，其中 $l$ 为 $s$ 最短非空平衡前缀，容易发现 $r$ 也是平衡串。考虑 $l$ 的合法性：
- 如果 $l$ 是合法的，那么 $\Phi(s)=l\Phi(r)$。
- 否则，$l$ 一定可以表示为 `)t(` 的形式，那么 $\Phi(s)=(\Phi(r))t^R$。
容易证明 $\Phi(s)$ 是一个合法括号串。
> **引理 3.0.1**. $\forall 2|n,0\le k\le n/2$，$\Phi$ 建立了 $D_{n,k}$ 到 $D_{n,0}$ 的双射。
**证明**：先证明单射。首先对 $n$ 归纳，命题对于 $n=0$ 显然成立。考虑两个串 $s_1,s_2\in D_{n,k}$ 且 $s_1\neq s_2$，分别将其分解为 $s_1=l_1r_1,s_2=l_2r_2$ 的形式，然后分类讨论：
- 情况 1：$l_1,l_2$ 都合法
此时 $l_1,l_2$ 分别为 $\Phi(s_1),\Phi(s_2)$ 的最短非空平衡前缀，如果 $l_1\neq l_2$ 那么命题成立，否则一定有 $r_1\neq r_2$，所以 $\Phi(r_1)\neq\Phi(r_2)$，命题成立。
- 情况 2：$l_1,l_2$ 都不合法
此时 $(\Phi(r_1)),(\Phi(r_2))$ 分别为 $\Phi(s_1),\Phi(s_2)$ 的最短非空平衡前缀，然后同理情况 1，命题成立。
- 情况 3：$l_1$ 合法，$l_2$ 不合法，设 $l_2=)t_2($。
此时 $l_1,(\Phi(r_2))$ 分别为 $\Phi(s_1),\Phi(s_2)$ 的最短非空平衡前缀。假设 $\Phi(s_1)=\Phi(s_2)$，那么一定有 $\Phi(r_1)=t_2^R$。因为 $l_1$ 合法，所以 $k=defect(s_1)=defect(r_1)$，$2k\le |r_1|=|\Phi(r_1)|=|t_2^R|<|l_2|$，也就是 $2k<|l_2|$。又因为 $l_2$ 是 $s_2$ 最短的非空平衡前缀，所以 $k=defect(s_2)\ge defect(l_2)$，即 $2k\ge |l_2|$，矛盾。
所以 $\Phi(s_1)\neq\Phi(s_2)$，命题成立。
- 情况 4：$l_1$ 不合法，$l_2$ 合法，和上面相同。
然后证明满射。因为有单射，所以对于所有 $0\le k\le n/2$ 有 $|D_{n,k}|\le |D_{n,0}|$，我们只需要证明 $|D_{n,k}|=|D_{n,0}|$。
假设存在 $0\le k\le n/2$ 满足 $|D_{n,k}|<|D_{n,0}|$，那么 $\dbinom n{n/2}=\sum\limits_{k=0}^{n/2}|D_{n,k}|<(n/2+1)|D_{n,0}|=\dbinom n{n/2}$，矛盾。
综上，$\forall 0\le k\le n/2$，$\Phi$ 建立了 $D_{n,k}$ 到 $D_{n,0}$ 的双射。$\square
有了引理 3.0.1，就可以十分方便地随机一个合法括号串了，只需要在所有平衡串中等概率随即一个然后对其使用 \Phi 即可。
哈希
哈希是 OI 中常用的通过较为随机的方式压缩信息来加速比较的算法。
通常情况下使哈希出错需要针对代码构造数据，然而有一些哈希方法是不需要针对代码就可以直接构造出错误数据的，而对拍用到的随机数据不足以发现这类问题。
下面列出几个常见的容易被构造出错的哈希算法。
生日悖论
一个房间中有 23 个人，一年有 365 天，且每个人的生日在这 365 天中独立等概率随机选取，问存在两个人同一天生日的概率是多少？
假设一年有 n 天，房间有 m 个人，那么这 m 个人生日互不相同的概率为 \prod\limits_{i=1}^m\dfrac{n-i+1}n。
代入 n=365,m=23 可得概率约为 49%，也就是存在两个人生日相同的概率大于 50%。
这是十分反直觉的，故我们称其为生日悖论。
那么 m 要达到多少才能让存在两个人生日相同的概率大于等于 50% 呢？列出如下方程：
\prod\limits_{i=1}^m\dfrac{n-i+1}n\le\dfrac 12
由 1+x\le e^x 进行估计：
\prod\limits_{i=1}^m e^{-\dfrac{i-1}n}\le\dfrac 12\\e^{-\dfrac{m(m-1)}{2n}}\le\dfrac 12
可以得到 m\approx\sqrt{2n\ln 2}。
一般的哈希方法是选择模数 M，将需要哈希的信息压缩到 [0,M-1] 内的整数。这个过程可以近似认为在 [0,M-1] 之间随机一个整数。
如果你要处理的问题形如“判断 n 条信息有无重复”，那么 n 约等于 \sqrt{2M\ln 2} 时将无重复信息判为有重复的概率会达到 \dfrac 12。
一般的单哈希模数在 10^9 级别，n 达到约 3\times 10^4 时就有约 36% 的概率出现冲突，这个概率是非常大的。这时应选用两个互质的模数 M_1,M_2，此时随机值域就可以看做 M_1M_2，将冲突概率大大减小。
自然溢出
字符串哈希时通常会选用模数 M 和进制 B。对于字符串 s=s_1s_2\dots s_n，其哈希值计算方法为：
hash(s)=\left(\sum\limits_{i=1}^n B^{i-1}\text{ord}(s_i)\right)\bmod M
其中 \text{ord}(c) 表示字符 c 在码表中的位置。
C++ 中的无符号 64 位整数在运算时会自动对 2^{64} 取模，如果选用 M=2^{64} 就可以少一次取模运算从而加快运行速度，这种哈希方法被称为自然溢出。
但这种哈希方法很容易构造冲突。如果 B 为偶数，那么 B^{64}\bmod M=0，也就是说 s 只有至多后 64 位有效，很容易构造冲突。下面讨论 B 为奇数的情况。
考虑如下字符串 s=s_1s_2\dots s_{2^k} 满足 s_i=\begin{cases}A&2\mid\text{popcount}(i-1)\\B&2\nmid\text{popcount}(i-1)\end{cases}。
对于字符串 t，设 t^F 表示将 t 中的 A 替换为 B，同时将 B 替换为 A 的结果。
考虑字符串序列 t_0,t_1,\dots,t_k 满足 t_0=A,t_i=t_{i-1}+t_{i-1}^F，那么 s=t_k。
设 d=\text{ord}(A)-\text{ord}(B)，那么
hash(s)-hash(s^F)\equiv\sum\limits_{i=1}^{2^k}(-1)^{\text{popcount}(i-1)}B^{i-1}d\pmod M
我们需要证明在 k 足够大时，这个值在 \bmod M 意义下总是等于 0。
设 f_i=hash(t_i)-hash(t_i^F)，容易得到 f_i=f_{i-1}(1-B^{2^{i-1}}) 而 f_0=d，于是有 f_i=d\prod\limits_{j=0}^{i-1}(1-B^{2^j})。
注意到 1-B^{2^j}=(1-B^{2^{j-1}})(1+B^{2^{j-1}})，也就是 1-B^{2^{j-1}} 乘上一个偶数，如果 2^p\mid(1-B^{2^{j-1}}) 那么一定有 2^{p+1}\mid(1-B^{2^j})，那么f_i 一定可以被 2^12^2\dots2^i=2^{\frac{i(i+1)}2} 整除。
## 树哈希
树哈希一般用于判断两棵有根树是否同构。
一种正确的树哈希方法应该递归求出一个子树 $u$ 的哈希值：
1. 求出 $u$ 的所有儿子的哈希值；
2. 将它们以（哈希值，子树大小）为关键字排序；
3. 排好序之后将它们的括号序依次相接；
4. 在最外层添加一对括号；
5. 得到的序列就是 $u$ 的括号序，其哈希值就是 $u$ 的哈希值。
容易证明同构的树的哈希值相同。
在第二步的排序关键字中加入子树大小是为了防止子树中因为生日悖论产生哈希值相同的大小不同的子树，影响结果。
设树的节点数为 $n$，因为要排序，所以以上算法的复杂度为 $\Theta(n\log n)$。还有一种复杂度为 $\Theta(n)$ 的哈希算法广为人知：记点 $u$ 的子树大小为 $sz_u$，儿子集合为 $son_u$。生成一个序列 $W_1\sim W_n$（一般采用质数序列或随机序列），点 $u$ 的哈希值计算如下：
$$h_u=W_{sz_u}(1+\sum\limits_{v\in son_u}h_v)$$
点 $u$ 到根节点路径上的 $sz$ 依次写出得到序列 $S_u$，那么整棵树的哈希值只与无序可重集 $H(T)=\{S_1,S_2,\dots,S_n\}$ 有关，集合相等的树得到的哈希值一定相等。
这种哈希的问题是，有时仅凭 $H(T)$ 无法唯一确定树的形态，例如下面两棵树无论 $W$ 如何选择，哈希值都相等。
实际上，只需要交换两个 $S$ 的相等的子树就可以保持 $H(T)$ 不变。上图交换了 $5$ 和 $9$ 的子树。
这组数据可以让所有只基于 $H(T)$ 的哈希算法出错。
# 总结
本文介绍的数据类型都是 OI 中较为常见的。
序列、树等数据类型，虽然容易生成，但是方法不当就容易构造出强度不够的数据。
仙人掌、括号串等数据类型，生成就存在一定难度。
而如果使用的哈希方法不当，有可能会在能够通过随机数据的情况下仍然丢失分数。
更多时候，选手需要根据题目性质构造更具针对性的数据，希望本文能引发大家的思考，对测试程序、构造数据的方法有进一步的理解。