AT_agc057_c.[AGC057C] Increment or Xor

给定一个正整数 $N$，以及一个长度为 $2^N$ 的数列 $A = (A_0, A_1, \ldots, A_{2^N-1})$。其中每个 $A_i$ 是 $0$ 到 $2^N-1$ 之间的整数，且对于 $i \neq j$，有 $A_i \neq A_j$。

你可以对数列 $A$ 进行以下两种操作：

• 操作 $+$：对所有 $i$，将 $A_i$ 变为 $(A_i + 1) \bmod 2^N$。
• 操作 $\oplus$：选择一个 $0$ 到 $2^N-1$ 之间的整数 $x$，对所有 $i$，将 $A_i$ 变为 $A_i \oplus x$。

这里的 $\oplus$ 表示按位异或（XOR）操作。

按位异或操作的定义如下：对于非负整数 $A, B$，$A \oplus B$ 的二进制表示中，每一位 $2^k$（$k \geq 0$）的数值，如果 $A$ 和 $B$ 的该位中只有一个为 $1$，则为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。

你的目标是通过若干次操作，使得对于所有 $i$，都有 $A_i = i$。请判断能否达成目标。如果可以，请输出一种不超过 $10^6$ 次操作的方案。

输入通过标准输入给出，格式如下：

$N$ $A_0$ $A_1$ $\ldots$ $A_{2^N-1}$

如果存在一种操作序列，使得对于所有 $i$，$A_i = i$，则输出 Yes，否则输出 No。

若输出 Yes，请继续输出一组操作序列，格式如下：

$K$ $x_1$ $x_2$ $\ldots$ $x_K$

其中 $K$ 表示操作次数，$0 \leq K \leq 10^6$。$x_i$ 表示第 $i$ 次操作：

• 若第 $i$ 次操作为 $+$，则 $x_i = -1$；
• 若第 $i$ 次操作为 $\oplus$，则 $x_i$ 为本次操作选择的整数 $x$。

如果存在多种方案，输出任意一种均可。

约束条件

• $1 \leq N \leq 18$
• $0 \leq A_i \leq 2^N - 1$
• 对于 $i \neq j$，有 $A_i \neq A_j$

样例解释 1

通过输出的操作序列，数列 $A$ 的变化如下：

• 初始状态：$A = (5,0,3,6,1,4,7,2)$
• 操作 $+$：$A = (6,1,4,7,2,5,0,3)$
• 操作 $\oplus$（$x = 6$）：$A = (0,7,2,1,4,3,6,5)$
• 操作 $+$：$A = (1,0,3,2,5,4,7,6)$
• 操作 $\oplus$（$x = 1$）：$A = (0,1,2,3,4,5,6,7)$

样例解释 2

无论如何操作，都无法达成目标。

样例解释 3

无需任何操作即可达成目标。空行的输出与判题结果无关。

由 ChatGPT 4.1 翻译