【MX-S5-T3】IMAWANOKIWA (Construction ver.)

原题链接：<https://oier.team/problems/91>。 --- [IMAWANOKIWA - いよわ / 初音ミク](https://www.bilibili.com/video/BV1iE411Y7bf) > あなたの未来が見たかった。

给你一个初始长度为 $n$，**只包含** $\boldsymbol{0, 1, 2}$ 的序列 $a_{1 \sim n}$，你可以执行以下操作： - 选择相邻的两个位置 $j$ 和 $j + 1$，删去 $a_j, a_{j + 1}$，并在原位置插入 $\mathrm{popc}(a_j + a_{j + 1})$，后半部分序列因此向前移动一位。其中，$\mathrm{popc}(x)$ 表示 $x$ 在二进制表示下 $1$ 的个数。 显然每次操作后序列长度都会减少 $1$，所以执行 $n - 1$ 次操作后，这个序列会恰好剩下一个数。 记在所有可能的 $n-1$ 次操作之后剩下的数的最小值为 $t$，定义一个好的操作序列 $p$ 为一个长度为 $n - 1$ 的正整数序列，其中 $p_i$ 表示第 $i$ 次操作所选择的 $j$（显然 $1 \le p_i \le n - i$），且满足按照这个操作序列操作之后剩下的数为 $t$，你需要求出 $t$ 与**字典序最小**的好的操作序列。 **如果你不会求出字典序最小的好的操作序列也可以获得部分分数**，详见【评分方式】。 为了避免输出量过大，你只需要输出字典序最小的好的操作序列按照某种哈希方式得到的哈希值即可，详见【输出格式】。

**本题有多组测试数据。** 第一行，一个正整数 $T$，表示数据组数。接下来，对于每组数据： - 仅一行，一个长度为 $n$ 的字符串，其中第 $i$ 个字符表示 $a_i$。

对于每组测试数据： - 输出一行，两个自然数 $t, \mathrm{Hash}(p')$，其中 - 第一个数表示剩下的数的最小值； - 第二个数表示字典序最小的好的操作序列 $p'$ 的哈希值 $\mathrm{Hash}(p')$，定义见下。 - 如果你输出的**第二个数不正确，也可以获得部分分数**，本题将使用**自定义校验器**做到这一点，详见【评分方式】。 > 令 $B = 13331$，$M = 2^{64}$，我们定义一个正整数序列 $c_{1 \sim l}$ 的哈希值 $\mathrm{Hash}(c)$ 为 $\sum_{i = 1}^l B^{l - i}c_i$ 对 $M$ 取模的结果。 > > 提示：代码实现时可以使用 C++ 的 `unsigned long long` 类型的自然溢出来实现对 $2^{64}$ 取模的效果。

7
110121
120202
1202
1121212
000
010101110
0112210112

1 31589928355420248
1 31587559229276557
2 177728893
2 15233797274127957404
0 13332
1 4098728445451629840
1 892964726593242284

**【样例解释 #1】** 对于第一组数据，字典序最小的好的操作序列 $p$ 为 $[1, 3, 2, 1, 1]$，按照该操作序列操作时，$a$ 序列的变化过程如下： $$ [1, 1, 0, 1, 2, 1]\\ [1, 0, 1, 2, 1]\\ [1, 0, 2, 1]\\ [1, 1, 1]\\ [1, 1]\\ [1] $$ 所以你应输出的哈希值为 $\mathrm{Hash}([1, 3, 2, 1, 1]) = (1 \times 13331^4 + 3 \times 13331^3 + 2 \times 13331^2 + 1 \times 13331^1 + 1 \times 13331^0) \bmod 2^{64} = 31589928355420248$。 对于第二组数据，字典序最小的好的操作序列 $p$ 为 $[1, 2, 2, 1, 1]$，按照该操作序列操作时，$a$ 序列的变化过程如下： $$ [1, 2, 0, 2, 0, 2]\\ [2, 0, 2, 0, 2]\\ [2, 1, 0, 2]\\ [2, 1, 2]\\ [2, 2]\\ [1] $$ **【样例 #2】** 见附件中的 `popc/popc2.in` 与 `popc/popc2.ans`。 该组样例共有十组测试数据，所有测试数据均满足 $n = 10^5$，其中测试数据 $1 \sim 5$ 满足序列 $a$ 中不存在 $0$，$6 \sim 10$ 满足序列 $a$ 中不存在 $1$。 **【样例 #3】** 见附件中的 `popc/popc3.in` 与 `popc/popc3.ans`。 该组样例共有四十组测试数据，其中测试数据 $1 \sim 10$ 满足 $n = 300$，$11 \sim 20$ 满足 $n = 3000$，$21 \sim 30$ 满足 $n = 3 \times 10^4$，$31 \sim 40$ 满足 $n = 10^5$。 **【评分方式】** 本题将使用**自定义校验器**计算你获得的部分分数。 对于一个测试点，如果你存在数据输出的最小值不正确，那么无法获得该测试点的分数。 对于一个测试点，如果你每组数据输出的最小值正确，但是存在数据求出的字典序最小的好的操作序列的哈希值不正确，那么可以获得该测试点 $25\%$ 的分数（即 $1$ 分，见【数据范围】）。**注意你仍需输出任意一个 $\boldsymbol{[0, 2^{64})}$ 内的整数表示你的方案的哈希值。** 对于一个测试点，如果你每组数据输出的最小值正确，且求出的字典序最小的好的操作序列的哈希值正确，那么可以获得该测试点的全部分数。 **【数据范围】** 对于所有测试数据，保证：$1 \le T \le 200$，$2 \le n \le 10^5$，序列 $a$ **只包含** $\boldsymbol{0, 1, 2}$。 | 测试点编号 | $T\le$ | $n\le$ | 特殊性质 | | :-: | :-: | :-: | :-: | | $1 \sim 3$ | $10$ | $10$ | 无 | | $4 \sim 6$ | $10$ | $300$ | 无 | | $7 \sim 9$ | $10$ | $3000$ | 无 | | $10 \sim 12$ | $10$ | $3 \times 10^4$ | 无 | | $13 \sim 15$ | $10$ | $10^5$ | 序列 $a$ 中不存在 $0$ | | $16 \sim 19$ | $10$ | $10^5$ | 序列 $a$ 中不存在 $1$ | | $20 \sim 21$ | $10$ | $10^5$ | 无 | | $22 \sim 23$ | $50$ | $10^5$ | 无 | | $24 \sim 25$ | $200$ | $10^5$ | 无 |