P17867 [FJCPC 2026] 哦 搞错了

昭老师以“经常出锅”闻名，这学期主讲《计算概论》。 他深谙《谢幕的教养》，常言：“开课是为了让学生学会，而不是要求老师学会。”秉持此理，他总在课末“谢幕”，将自己都没搞懂的问题直接抛给学生当作业。 本周作业是“全局异或光线追踪”的逆向构造。题目刚出，便有同学指出：“根据题目性质，这个在数学上根本无法完美构造！” 昭老师敲着讲台坚称：“我检查过，绝对有解！” 五分钟后，他在同学的提醒下才意识到错误。 :::align{center} **“哦 搞错了。”** ::: 为了掩饰尴尬，昭老师迅速修改了作业规则。 选了这门课的大聪明正忙着用刚刚购入的周处英雄打三国杀，现在就请你编写程序，完成这道修改后的作业。

**形式化地说**，给定一个长度为 $N$ 的 $01$ 字符串 $S$ ，请构造一个长度为 $N$ 的正整数数组 $A$ ，满足以下条件： - 对于任意 $1 \leq i \leq N$ ，有 $0 < A_i < 2^{60}$。 - 对于任意 $i \neq j$ ，有 $A_i \neq A_j$。 记全局异或和为 $$ X = A_1 \oplus A_2 \oplus \dots \oplus A_N. $$ 再定义一个长度为 $N$ 的 $01$ 字符串 $W$ 。对于每个 $1 \leq i \leq N$： - 若 $A_i \oplus X < A_i$，则 $W_i = 1$； - 否则 $W_i = 0$。 要求字符串 $W$ 与字符串 $S$ 的海明距离不超过 $1$，即 $$ \sum_{i = 1}^{N} [W_i \neq S_i] \leq 1. $$ 输出任意一组满足条件的解即可。可以证明，在本题数据范围内这样的解总是存在。 本题中，异或运算记作 $\oplus$ ，定义如下：对于两个非负整数 $a,b$ ，设它们的二进制展开分别为 $$ a = \sum_{k \geq 0} a_k 2^k, \quad b = \sum_{k \geq 0} b_k 2^k, $$ 其中 $a_k, b_k \in \{0,1\}$ ，且只有有限多个二进制位为1。定义 $$ a \oplus b = \sum_{k \geq 0} c_k 2^k, \quad c_k = (a_k + b_k) \bmod 2. $$ 也就是说，每一位上两个数不同则结果为 $1$，相同则结果为 $0$。多个整数的异或和按该二元运算依次计算；异或运算满足结合律和交换律，因此计算顺序不影响结果。

输入一行一个字符串 $S$ （$1 \leq |S| \leq 10^5$），仅由字符 `0` 和 `1` 组成。令 $N = |S|$。

输出一行 $N$ 个以空格分隔的正整数，表示你构造的数组 $A$。 输出的数组必须满足： - 对于任意 $1 \leq i \leq N$ ，有 $0 < A_i < 2^{60}$。 - 对于任意 $i \neq j$ ，有 $A_i \neq A_j$。 - 按题意由 $A$ 生成的字符串 $W$ 与输入字符串 $S$ 的海明距离不超过 $1$。 如果存在多组合法答案，输出任意一组即可。

样例输出并不唯一。 在第一组样例中，输出数组为 $[1,2]$，它的全局异或和为 $$ X = 1 \oplus 2 = 3. $$ 由于 $1 \oplus 3 = 2 > 1$，所以 $W_1 = 0$；由于 $2 \oplus 3 = 1 < 2$，所以 $W_2 = 1$。因此生成的字符串为 $W = 01$，与输入串完全相同。 在第二组样例中，输出数组为 $$ [15, 86, 66, 69, 20, 68]. $$ 它的全局异或和为 $$ X = 15 \oplus 86 \oplus 66 \oplus 69 \oplus 20 \oplus 68 = 14. $$ 逐项判断： - $15 \oplus 14 = 1 < 15$ → $W_1 = 1$ - $86 \oplus 14 = 88 > 86$ → $W_2 = 0$ - $66 \oplus 14 = 76 > 66$ → $W_3 = 0$ - $69 \oplus 14 = 75 > 69$ → $W_4 = 0$ - $20 \oplus 14 = 26 > 20$ → $W_5 = 0$ - $68 \oplus 14 = 74 > 68$ → $W_6 = 0$ 因此生成的字符串为 $W = 100000$，与输入串 $S = 100001$ 仅第六位不同，海明距离为 $1$ ，满足要求。