分数: 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 否则。
约束
- 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 通过执行以下操作:
- 选择 i=2. A 变为 分别为 (2,7,7).
- 选择 i=1. A 变为 分别为 (5,5,7).
对于第二个测试用例,您可以 A_1=0 通过执行以下操作:
- 选择 i=1. A 变为 分别为 (1,1,4).
- 选择 i=1. A 变为 分别为 (0,0,4).
- 选择 i=1. A 变为 分别为 (0,0,4).
对于第三个测试用例,不可能使 A_1=8 最多 10^4 操作。