CF2183I2 Pairs Flipping (Hard Version)

这是该问题的难度较高版本。不同之处在于，在本版本中，对于最终字符串中剩余 $1$ 的数量的限制更加严格。只有在解决了该问题的所有版本后，才可以进行 Hack。 给定一个仅包含 $0$ 和 $1$ 的二进制字符串 $s_1s_2\ldots s_n$。你可以进行 $ \lfloor\frac{n}{2}\rfloor $ 次操作。在第 $x$ 次操作时，你可以执行以下操作： - 选择一个整数 $l$，其中 $0 \leq l \leq n-x$。如果 $l=0$，则什么也不做。否则，将字符 $s_l$ 和 $s_{l+x}$ 都进行反转。也就是说，对于每个字符，如果原本是 $0$，则变为 $1$，如果原本是 $1$，则变为 $0$。 你的任务是找到一系列操作，使得操作结束后，二进制字符串中剩余的 $1$ 的个数不超过 $7$。可以证明，在本题的约束条件下，总能做到这一点。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 2 \cdot 10^6$）。 第二行包含一个二进制字符串 $s_1s_2\ldots s_n$（$s_i \in \{0,1\}$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^6$。

对于每个测试用例，输出 $ \lfloor\frac{n}{2}\rfloor $ 个数，分别为第 $1$ 次操作到第 $\lfloor\frac{n}{2}\rfloor $ 次操作选择的 $l$，满足 $0 \leq l_x \leq n - x$。你需要保证在所有操作结束后，字符串中剩余的 $1$ 的个数不超过 $7$。 如果有多种方案，输出任意一种即可。

以第四组测试数据为例： - 初始字符串 $s = 111111111$。由于 $n=9$，因此可以进行 $ \lfloor\frac{9}{2}\rfloor = 4 $ 次操作。 - 第一次操作选择 $l=6$，即反转第 $6$ 和第 $6+1=7$ 个字符。此时，$s = 111110011$。 - 第二次操作选择 $l=2$，即反转第 $2$ 和第 $2+2=4$ 个字符。此时，$s = 101010011$。 - 第三次操作选择 $l=0$，即不做任何操作。 - 第四次操作选择 $l=2$，即反转第 $2$ 和第 $2+4=6$ 个字符。此时，$s=111011011$。 - 最终字符串中有 $7$ 个 $1$，并且 $7 \leq 7$，因此该方案正确。 由 ChatGPT 5 翻译