4060. IMAWANOKIWA

【题目背景】

【题目描述】

给你一个初始长度为 n，只包含 0,1,2 的序列 a1∼n，你可以执行以下操作：选择相邻的两个位置 j 和 j+1，删去 aj,aj+1，并在原位置插入 popc(aj+aj+1)，后半部分序列因此向前移动一位。其中，popc(x) 表示 x 在二进制表示下 1 的个数。显然每次操作后序列长度都会减少 1，所以执行 n−1 次操作后，这个序列会恰好剩下一个数。

记在所有可能的 n−1 次操作之后剩下的数的最小值为 t，定义一个好的操作序列 p 为一个长度为 n−1 的正整数序列，其中 pi 表示第 i 次操作所选择的 j（显然 1≤pi≤n−i），且满足按照这个操作序列操作之后剩下的数为 t，你需要求出 t 与字典序最小的好的操作序列。

如果你不会求出字典序最小的好的操作序列也可以获得部分分数，详见【评分方式】。

为了避免输出量过大，你只需要输出字典序最小的好的操作序列按照某种哈希方式得到的哈希值即可，详见【输出格式】。

【输入格式】

本题有多组测试数据。

第一行，一个正整数 T，表示数据组数。接下来，对于每组数据：仅一行，一个长度为 n 的字符串，其中第 i 个字符表示 ai。

【输出格式】

对于每组测试数据：输出一行，两个自然数 t, Hash(p′)，其中第一个数表示剩下的数的最小值；第二个数表示字典序最小的好的操作序列 p′ 的哈希值 Hash(p′)，定义见下。如果你输出的第二个数不正确，也可以获得部分分数，本题将使用自定义校验器做到这一点，详见【评分方式】。令 B=13331，M=264，我们定义一个正整数序列 c1∼l 的哈希值 Hash(c) 为 ∑i=1lBl−ici 对 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

【样例说明】

对于第一组数据，字典序最小的好的操作序列 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]

所以你应输出的哈希值为Hash([1,3,2,1,1])=(1×13331^4+3×13331^3+2×13331^2+1×13331^1+1×13331^0) mod 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]

【数据规模与约定】

在此键入。

【来源】

在此键入。