AT_arc145_e [ARC145E] Adjacent XOR
题目描述
给定两个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$。
请判断是否可以通过不超过 $70000$ 次如下操作,将序列 $A$ 变为序列 $B$。如果可以,请给出一种实际的操作方案。
- 选择一个整数 $K\ (1\leq K \leq N)$。对于所有 $i\ (2\leq i \leq K)$,将 $A_i$ 的值替换为 $A_{i-1} \oplus A_i$。该替换对所有满足条件的 $i$ 同时进行。
这里,$\oplus$ 表示按位异或(XOR)运算。
按位异或(XOR)运算定义如下:对于非负整数 $A,B$,$A\oplus B$ 的二进制表示中,每一位的值等于 $A,B$ 在该位上的值仅有一个为 $1$ 时为 $1$,否则为 $0$。
例如,$3\oplus 5 = 6$(二进制为:$011\oplus 101 = 110$)。
输入格式
输入通过标准输入给出,格式如下:
> $N$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$
输出格式
如果无法在 $70000$ 次操作内将 $A$ 变为 $B$,输出 `No`。
如果可以,设操作次数为 $M$,第 $i$ 次操作选择的整数为 $K_i$,则输出如下格式:
> Yes $M$ $K_1$ $K_2$ $\ldots$ $K_M$
如果存在多种满足条件的方案,输出任意一种均可。
说明/提示
### 限制条件
- $2 \leq N \leq 1000$
- $0 \leq A_i, B_i < 2^{60}$
- 所有输入均为整数
### 样例解释 1
在该输出样例中,序列 $A$ 经过如下变化:
- 初始状态:$A=(1,\,2,\,0)$
- 第 $1$ 次操作后:$A=(1,\,3,\,0)$
- 第 $2$ 次操作后:$A=(1,\,2,\,3)$
经过 $2$ 次操作后,$A$ 与 $B$ 完全一致,因此该输出满足条件。
由 ChatGPT 4.1 翻译