AtCoder Regular Contest 199 (Div. 1)
B
Adjacent Replace
AtCoder
⌀ 2212
原题
← AC →
翻译中…

Problem Statement

翻译中…

You are given a sequence of non-negative integers of length $N$: $A=(A_1,A_2,\ldots,A_N)$ and a non-negative integer $K$.

翻译中…

Determine whether it is possible to make $A_1=K$ by performing the following operation at most $10^4$ times:

翻译中…
  • Choose an integer $i\ (1\leq i\leq N-1)$. Let $x=A_i\oplus A_{i+1}$, then replace both $A_i,A_{i+1}$ with $x$.
翻译中…

Here, $\oplus$ denotes the bitwise XOR operation.

翻译中…

If possible, output one such sequence of operations.

翻译中…

You are given $T$ test cases, so solve each of them.

翻译中…

What is bitwise XOR operation? The bitwise XOR of non-negative integers $A, B$, denoted $A \oplus B$, is defined as follows: When $A \oplus B$ is written in binary, the digit in the $2^k$ ($k \geq 0$) place is $1$ if exactly one of $A, B$ has $1$ in the $2^k$ place when written in binary, and $0$ otherwise. For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).

翻译中…

Constraints

翻译中…
  • $1\leq T\leq 50$
  • $3\leq N\leq 60$
  • $0\leq A_i,K\lt 2^{60}$
  • All input values are integers.
翻译中…

Input

翻译中…

The input is given from Standard Input in the following format:

翻译中…

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

翻译中…

Each test case is given in the following format:

翻译中…

N K
A_1 A_2 \ldots A_N

翻译中…

Output

翻译中…

Output your solutions for $\mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T$ in order in the following format:

翻译中…

If it is impossible to make $A_1=K$ by performing the operation at most $10^4$ times, output No.

翻译中…

If possible, output the sequence of operations in the following format:

翻译中…

Yes
M
i_1 i_2 \ldots i_M

翻译中…

Here, $M$ is the number of operations, and $i_j\ (1\leq j\leq M)$ represents the integer $i$ chosen in the $j$-th operation. You need to satisfy $0\leq M\leq 10^4, 1\leq i_j\leq N-1$.

翻译中…

If there are multiple sequences of operations that satisfy the conditions, any of them will be considered correct.

翻译中…

样例

Input #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
Output #1
Yes
2
2 1
Yes
3
1 1 1
No
Yes
0

Yes
4
2 3 2 1
For the first test case, you can make $A_1=5$ by performing the operations as follows: 1. Choose $i=2$. $A$ becomes $(2,7,7)$. 2. Choose $i=1$. $A$ becomes $(5,5,7)$. For the second test case, you can make $A_1=0$ by performing the operations as follows: 1. Choose $i=1$. $A$ becomes $(1,1,4)$. 2. Choose $i=1$. $A$ becomes $(0,0,4)$. 3. Choose $i=1$. $A$ becomes $(0,0,4)$. For the third test case, it is impossible to make $A_1=8$ with at most $10^4$ operations.
题目信息
题号
arc199_b
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。