题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

在一个字符串中，选择一个或多个连续位置的字符，并保持其顺序排列后得到的字符串，称为该字符串的子字符串。
例如，$\tt{001}$ 是字符串 $X = \tt{10011}$ 的子字符串，但不是字符串 $Y = \tt{10101}$ 的子字符串。

两个非负整数 $A$ 和 $B$ 的异或（XOR）$A \oplus B$ 定义如下：

• 从二进制的角度来看，若 $A$ 的第 $2^k$ 位与 $B$ 的第 $2^k$ 位不同，则 $A \oplus B$ 的第 $2^k$ 位为 1；若相同，则该位为 0。（其中 $k \ge 0$）
• 例如，$12 \oplus 10$ 的计算如下：
  $12 = 1100_2$，$10 = 1010_2$，因此
  $1100_2 \oplus 1010_2 = 0110_2 = 6$

给定一个仅由 0 和 1 组成、长度为 $N$ 的字符串 $S$。
你需要计算从 $S$ 的子字符串 $s_1$ 和 $s_2$ 中可以构造出的 $g(s_1, s_2)$ 的最大值。函数 $g(s_1, s_2)$ 定义如下：

• 对于 $S$ 的子字符串 $s$，$f(s)$ 表示将 $s$ 视为二进制数后对应的十进制数值。例如，若 $s = 11010$，则 $f(s) = 26$。
• $g(s_1, s_2) = f(s_1) \oplus f(s_2)$

此处 $s_1$ 和 $s_2$ 不需要不同。换句话说，$s_1$ 和 $s_2$ 可以在 $S$ 中部分重叠，甚至可以是完全相同的字符串。

给定一个仅由 0 和 1 组成的字符串 $S$，请编写一个程序来计算可能的 $g(s_1, s_2)$ 的最大值。

输入格式

第一行输入测试用例的个数 $T$。
接下来的每个测试用例包含两行：

• 第一行：字符串长度 $N$
• 第二行：一个长度为 $N$ 的仅由 0 和 1 组成的字符串 $S$

输出格式

对于每个测试用例，输出可能的 $g(s_1, s_2)$ 的最大值，用二进制表示，每行输出一个结果。
注意，结果前不应输出无意义的前导 0。

4
3
010
5
10101
5
00100
5
11111

11
11111
110
11110

4
2
00
2
01
2
10
2
11

0
1
11
10

提示

样例 1 说明

在第一个测试用例中，将 $s_1 = 010$，$s_2 = 01$，可以得到 $g(s_1, s_2) = 11_2$。
尽管也可以写作 $011_2$，但因为不能有无意义的前导 0，因此应输出 11，而不是 011。

在第四个测试用例中，将 $s_1 = 11111$，$s_2 = 1$，可以得到 $g(s_1, s_2) = 11110_2$。

约束条件

• 所有给定数均为整数。
• $1 \le T \le 100$
• $2 \le N \le 10^7$
• 所有测试用例中 $N$ 的总和 $\le 10^7$
• $S$ 是一个由 0 和 1 组成、长度为 $N$ 的字符串。

子问题

1. （17 分）$N \le 30$，所有测试用例中 $N$ 的总和 $\le 300$
2. （20 分）$N \le 200$，所有测试用例中 $N$ 的总和 $\le 2000$
3. （13 分）$N \le 3000$，所有测试用例中 $N$ 的总和 $\le 30000$
4. （12 分）$N \le 2 \times 10^5$，所有测试用例中 $N$ 的总和 $\le 2 \times 10^6$
5. （38 分）无额外约束条件

翻译由 ChatGPT-4o 完成