EOJ Test Round #6

有一个 01 字符串家族 $s_i$ 按如下定义：

• $s_0 = 0$;
• $s_i = s_{i-1} + anti(s_{i-1})$.

其中 $+$ 表示字符串的连接操作，$anti$ 表示对 01 字符串进行取反（原来 0 的变成 1，原来 1 的变成 0）。

按照这样的规则：

• $s_0 = 0$,
• $s_1 = 01$,
• $s_2 = 0110$,
• $s_3 = 01101001$,
• $s_4 = 0110100110010110$,
• ......

这些字符串拥有诸多神奇的性质。例如：

1. 任意一个之前出现的字符串都是当前字符串的前缀（由定义保证）。
2. $s_0, s_2, s_4, \ldots$ 是对称的，$s_1,s_3,s_5$ 是反对称的。
3. 如果对某一个字符串的下标和下标上的数进行研究，你会发现是 0 还是 1 实质上与下标二进制上 1 的个数的奇偶性有关。
4. 取二进制串对应的子集，例如 $s_4$ 对应于 $A={2,3,5,8,9,12,14,15}$，$anti(s_4)$ 对应于 $A’={1,4,6,7,10,11,13,16}$，则 $A+A=A’+A’$。其中 $A+A={x + y | x, y \in A, x \neq y}$。不相信吗？可以取 $s_2$ 验证一下。
5. $n \ge 13$ 时可以卡掉基于自然溢出的字符串哈希。