P9851 [ICPC 2021 Nanjing R] Secret of Tianqiu Valley

在天穹谷遗迹的北塔中，有一些火炬谜题，旅行者荧正面临最后一个也是最难的一个。 在一个圆圈中有 $n$ 个火炬，初始时有些火炬已经被点燃。对于所有 $1 \le i \le n$，第 $i$ 个和第 $(i \bmod n +1)$ 个火炬是相邻的。 为了破解这个谜题，所有的火炬都应该被点燃。在每一步中，荧可以点燃一个熄灭的火炬，并且受超自然力量影响，相邻火炬的状态将被反转。也就是说，如果相邻火炬当前是熄灭的，它将被点燃；如果当前是点燃的，它将被熄灭。 时间就是金钱，荧希望在 $2n$ 步内解决这个谜题，或者确定这个谜题是无法解决的。

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例： 输入的第一行包含一个整数 $n$ ($3 \le n \le 10^5$)，表示圆圈中火炬的数量。 第二行包含一个长度为 $n$ 的二进制字符串 $s_1s_2\cdots s_n$ ($s_i \in \{\text{`0'}, \text{`1'}\}$)。如果 $s_i = \text{`0'}$，则第 $i$ 个火炬初始时是熄灭的；如果 $s_i = \text{`1'}$，则第 $i$ 个火炬初始时是点燃的。保证初始时并非所有火炬都被点燃。 还保证所有测试用例的 $n$ 之和不超过 $10^6$。

如果谜题无法解决，输出 `0`。 否则，第一行输出一个整数 $k$ $(1 \le k \le 2n)$，表示荧需要的移动次数。然后输出一行包含 $k$ 个用空格分隔的整数 $t_1, t_2, \cdots, t_k$，其中 $t_i$ 表示荧将在第 $i$ 次移动中点燃第 $t_i$ 个火炬。如果有多个答案，输出任意一个。 请不要在每行的末尾输出多余的空格，否则您的解决方案可能被认为不正确！

对于第一个样例测试用例，火炬的状态将如下变化：$00000$ $\to$ $11100$ $\to$ $01111$ $\to$ $10110$ $\to$ $01010$ $\to$ $00100$ $\to$ $00011$ $\to$ $11111$。 题面翻译由 ChatGPT-4o 提供。