← 返回题目列表

AtCoder · arc199_b

B. 相邻替换

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

分数: 800 点

问题陈述

给定一个长度为非负整数的序列 N: A=(A_1,A_2,\ldots,A_N) 和一个非负整数 K.

判断是否可以使 A_1=K 最多执行以下操作 10^4 次:

  • 选择一个整数 i\ (1\leq i\leq N-1)。让 x=A_i\oplus A_{i+1},然后替换两者 A_i,A_{i+1} 与 x.

在这里, \oplus 表示按位异或运算。

如果可能,输出这样的操作序列。

你被给予 T 测试用例,因此解决每个用例。

什么是按位异或运算?

非负整数的按位异或 A, B,表示 A \oplus B,定义如下:

  • 当 A \oplus B 以二进制形式写入,其中的数字 2^k (k \geq 0) 地方是 1 如果恰好是以下之一 当以二进制形式写入时,位于 A, B 有 1 在 2^k 位置,并且 0 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).

约束

  • 1\leq T\leq 50
  • 3\leq N\leq 60
  • 0\leq A_i,K\lt 2^{60}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N K
A_1 A_2 \ldots A_N

输出

输出您的解决方案 \mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T 按以下格式顺序排列:

如果不可能 A_1=K 最多执行该操作 10^4 次,输出 No.

如果可能,按以下格式输出操作序列:

Yes
M
i_1 i_2 \ldots i_M

在这里, M 是操作次数,并且 i_j\ (1\leq j\leq M) 代表整数 i 选择于 j第次操作。你需要满足 0\leq M\leq 10^4, 1\leq i_j\leq N-1.

如果存在多个满足条件的操作序列,则其中任何一个都将被认为是正确的。


示例输入 1

5
3 5
2 3 4
3 0
2 3 4
3 8
2 3 4
3 2
2 3 4
4 10
2 3 4 8

示例输出 1

Yes
2
2 1
Yes
3
1 1 1
No
Yes
0

Yes
4
2 3 2 1

对于第一个测试用例,您可以 A_1=5 通过执行以下操作:

  1. 选择 i=2. A 变为 分别为 (2,7,7).
  2. 选择 i=1. A 变为 分别为 (5,5,7).

对于第二个测试用例,您可以 A_1=0 通过执行以下操作:

  1. 选择 i=1. A 变为 分别为 (1,1,4).
  2. 选择 i=1. A 变为 分别为 (0,0,4).
  3. 选择 i=1. A 变为 分别为 (0,0,4).

对于第三个测试用例,不可能使 A_1=8 最多 10^4 操作。