P11269 [MX-S5-T3] IMAWANOKIWA (Construction ver.)

Original problem link: 。 --- [IMAWANOKIWA - Iyowa / Hatsune Miku](https://www.bilibili.com/video/BV1iE411Y7bf) > あなたの未来が見たかった。

You are given a sequence $a_{1 \sim n}$ of initial length $n$ that **contains only** $\boldsymbol{0, 1, 2}$. You can perform the following operation: - Choose two adjacent positions $j$ and $j + 1$, delete $a_j, a_{j + 1}$, and insert $\mathrm{popc}(a_j + a_{j + 1})$ at the original position. The second half of the sequence therefore shifts forward by one position. Here, $\mathrm{popc}(x)$ denotes the number of $1$'s in the binary representation of $x$. Obviously, after each operation the sequence length decreases by $1$, so after performing $n - 1$ operations, the sequence will end up with exactly one number. Let the minimum possible remaining number after all possible sequences of $n - 1$ operations be $t$. Define a good operation sequence $p$ as a positive integer sequence of length $n - 1$, where $p_i$ denotes the chosen $j$ in the $i$-th operation (clearly $1 \le p_i \le n - i$), and after performing operations according to this sequence, the remaining number equals $t$. You need to output $t$ and the **lexicographically smallest** good operation sequence. **If you cannot find the lexicographically smallest good operation sequence, you can still get partial points**, see [Scoring] for details. To avoid excessive output, you only need to output the hash value of the lexicographically smallest good operation sequence under a certain hashing method, see [Output Format] for details.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. Then for each test case: - A single line containing a string of length $n$, where the $i$-th character represents $a_i$.

For each test case: - Output one line with two non-negative integers $t, \mathrm{Hash}(p')$, where - The first number is the minimum possible remaining number. - The second number is the hash value $\mathrm{Hash}(p')$ of the lexicographically smallest good operation sequence $p'$, defined below. - **Even if the second number you output is incorrect, you can still get partial points**, and the problem will use a **custom checker** to do this. See [Scoring] for details. > Let $B = 13331$ and $M = 2^{64}$. We define the hash value $\mathrm{Hash}(c)$ of a positive integer sequence $c_{1 \sim l}$ as $\sum_{i = 1}^l B^{l - i}c_i$ modulo $M$. > > Hint: In code, you can use the natural overflow of C++ type `unsigned long long` to achieve the modulo $2^{64}$ effect.

**[Sample Explanation #1]** For the first test case, the lexicographically smallest good operation sequence $p$ is $[1, 3, 2, 1, 1]$. When performing operations according to this sequence, the changes of sequence $a$ are as follows: $$ [1, 1, 0, 1, 2, 1]\\ [1, 0, 1, 2, 1]\\ [1, 0, 2, 1]\\ [1, 1, 1]\\ [1, 1]\\ [1] $$ So the hash value you should output is $\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$. For the second test case, the lexicographically smallest good operation sequence $p$ is $[1, 2, 2, 1, 1]$. When performing operations according to this sequence, the changes of sequence $a$ are as follows: $$ [1, 2, 0, 2, 0, 2]\\ [2, 0, 2, 0, 2]\\ [2, 1, 0, 2]\\ [2, 1, 2]\\ [2, 2]\\ [1] $$ **[Sample #2]** See `popc/popc2.in` and `popc/popc2.ans` in the attachments. This sample contains ten test cases. All test cases satisfy $n = 10^5$. Among them, test cases $1 \sim 5$ satisfy that there is no $0$ in sequence $a$, and test cases $6 \sim 10$ satisfy that there is no $1$ in sequence $a$. **[Sample #3]** See `popc/popc3.in` and `popc/popc3.ans` in the attachments. This sample contains forty test cases. Among them, test cases $1 \sim 10$ satisfy $n = 300$, $11 \sim 20$ satisfy $n = 3000$, $21 \sim 30$ satisfy $n = 3 \times 10^4$, and $31 \sim 40$ satisfy $n = 10^5$. **[Scoring]** This problem will use a **custom checker** to compute your partial score. For a test point, if there exists any testdata where the minimum value you output is incorrect, then you cannot get any score for this test point. For a test point, if the minimum value you output is correct for every test case, but there exists some testdata where the hash value of the lexicographically smallest good operation sequence you computed is incorrect, then you can get $25\%$ of the score for this test point (i.e. $1$ point, see [Constraints]). **Note that you still need to output any integer within $\boldsymbol{[0, 2^{64})}$ as the hash value of your solution.** For a test point, if the minimum value you output is correct for every test case, and the hash value of the lexicographically smallest good operation sequence you computed is also correct, then you can get the full score for this test point. **[Constraints]** For all testdata, it is guaranteed that $1 \le T \le 200$, $2 \le n \le 10^5$, and sequence $a$ **contains only** $\boldsymbol{0, 1, 2}$. | Test Point ID | $T\le$ | $n\le$ | Special Property | | :-: | :-: | :-: | :-: | | $1 \sim 3$ | $10$ | $10$ | None | | $4 \sim 6$ | $10$ | $300$ | None | | $7 \sim 9$ | $10$ | $3000$ | None | | $10 \sim 12$ | $10$ | $3 \times 10^4$ | None | | $13 \sim 15$ | $10$ | $10^5$ | No $0$ in sequence $a$ | | $16 \sim 19$ | $10$ | $10^5$ | No $1$ in sequence $a$ | | $20 \sim 21$ | $10$ | $10^5$ | None | | $22 \sim 23$ | $50$ | $10^5$ | None | | $24 \sim 25$ | $200$ | $10^5$ | None | Translated by ChatGPT 5