← 返回题目列表

AtCoder · arc145_e

E. 相邻异或

中文机器翻译题面 查看原题

分数: 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