分数: 800 点
问题陈述
给你两个序列,每个序列的长度 N,由非负整数组成: A=(A_1,A_2,\ldots,A_{N}) 和 B=(B_1,B_2,\ldots,B_{N}).
判断是否可以使 A 等于 B 最多执行以下操作 70000 次。如果可能,请提出实现该目标的特定操作顺序。
- 选择一个整数 K\ (1\le K \le N)。对于每个整数 i\ (2\leq i \leq K),同时替换 A_i 与 A_{i-1} \oplus A_i.
在这里, \oplus 表示按位 \mathrm{XOR}.
什么是按位 \mathrm{XOR}?
按位 非负整数的 \mathrm{XOR} 非负整数的 A 和 B, A\oplus B,定义如下:
- 当 A\oplus B 以基数 2 书写,即 2^k的地点 (k \geq 0) 是 1 如果恰好是该位置的数字之一 A 和 B 是 1,和 0 否则。
例如, 3\oplus 5 = 6 (以二为基数: 011\oplus 101 = 110).
约束
- 2 \leq N \leq 1000
- 0 \leq A_i, B_i < 2^{60}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
输出
如果不可能 A 等于 B 最多 70000 操作,打印 No。如果可能的话,以以下格式打印实现它的操作序列,其中 M 是操作次数,并且 K_i 是在中选择的整数 i第操作:
Yes M K_1 K_2 \ldots K_M
如果存在多个解决方案,则将接受其中任何一个。
样本输入 1
3 1 2 0 1 2 3
示例输出 1
Yes 2 2 3
在此输出中,序列 A 变更如下:
- 最初: A=(1, 2, 0).
- 之后 1-st 操作: A=(1, 3, 0).
- 之后 2-nd操作: A=(1, 2, 3).
两次操作后, A 和 B 是平等的,实现了目标。
示例输入 2
2 10 100 1 0
示例输出 2
No
示例输入 3
2 1152921504606846975 0 1152921504606846975 0
示例输出 3
Yes 0