/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1100 点
問題文
正整数 N および、2^N 項からなる数列 A = (A_0, A_1, \ldots, A_{2^N-1}) が与えられます。ここで各 A_i は 0 以上 2^N-1 以下の整数であり、i\neq j ならば A_i\neq A_j が成り立ちます。
あなたは数列 A に対して、次の 2 種類の操作を行うことができます：
- 操作 +：すべての i に対して、A_i を (A_i + 1) \bmod 2^N に変更する。
- 操作 \oplus：0 以上 2^N-1 以下の整数 x を選ぶ。すべての i に対して A_i を A_i\oplus x に変更する。
ただしここで、\oplus はビット単位 \mathrm{XOR} 演算を表します。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
あなたの目的は、すべての i に対して A_i = i が成り立つようにすることです。目的を達成することが可能であるかを判定してください。本問題の制約下では、目的を達成することが可能な場合には、操作回数を 10^6 回以下にできることが証明できます。そのような操作列を出力してください。
制約
- 1\leq N\leq 18
- 0\leq A_i \leq 2^N - 1
- i\neq j ならば A_i\neq A_j
入力
入力は以下の形式で標準入力から与えられます。
N
A_0 A_1 \ldots A_{2^N - 1}
出力
すべての i に対して A_i = i が成り立つようにすることが可能ならば Yes、そうでなければ No を出力してください。
Yes の場合には、さらに目的を達成するための操作列を次の形式で出力してください。
K x_1 x_2 \ldots x_K
ここで K は操作の回数を表す非負整数で、0\leq K\leq 10^6 を満たす必要があります。また、x_i は i 回目の操作を表す整数で、
- i 回目に操作 + を行う場合には、x_i=-1
- i 回目に操作 \oplus を行う場合には、x_i はその操作で選ぶ整数 x
と定めてください。
答が複数考えられる場合には、そのどれを出力しても正解となります。
入力例 1
3 5 0 3 6 1 4 7 2
出力例 1
Yes 4 -1 6 -1 1
出力の操作列によって、数列 A は次のように変化します。
- 初期状態：A = (5,0,3,6,1,4,7,2)
- 操作 +：A = (6,1,4,7,2,5,0,3)
- 操作 \oplus (x = 6)：A = (0,7,2,1,4,3,6,5)
- 操作 +：A = (1,0,3,2,5,4,7,6)
- 操作 \oplus (x = 1)：A = (0,1,2,3,4,5,6,7)
入力例 2
3 2 5 4 3 6 1 0 7
出力例 2
No
どのように操作を行っても、目的を達成することはできません。
入力例 3
3 0 1 2 3 4 5 6 7
出力例 3
Yes 0
0 回の操作により目的が達成できます。なお、空行の出力の有無は、ジャッジ結果に影響しません。
Score : 1100 points
Problem Statement
You are given a positive integer N and a sequence A = (A_0, A_1, \ldots, A_{2^N-1}) of 2^N terms, where each A_i is an integer between 0 and 2^N-1 (inclusive) and A_i\neq A_j holds if i\neq j.
You can perform the following two kinds of operations on A:
- Operation +: For every i, change A_i to (A_i + 1) \bmod 2^N.
- Operation \oplus: Choose an integer x between 0 and 2^N-1. For every i, change A_i to A_i\oplus x.
Here, \oplus denotes bitwise \mathrm{XOR}.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows:
- When A \oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
Your objective is to make A_i = i for every i. Determine whether it is achievable. It can be proved that, under the Constraints of this problem, one can achieve the objective with at most 10^6 operations if it is achievable at all. Print such a sequence of operations.
Constraints
- 1\leq N\leq 18
- 0\leq A_i \leq 2^N - 1
- A_i\neq A_j, if i\neq j
Input
Input is given from Standard Input in the following format:
N
A_0 A_1 \ldots A_{2^N - 1}
Output
If it is possible to make A_i = i for every i, print Yes; otherwise, print No.
In the case of Yes, it should be followed by a sequence of operations that achieves the objective, in the following format:
K x_1 x_2 \ldots x_K
Here, K is a non-negative integer representing the number of operations, which must satisfy 0\leq K\leq 10^6; x_i is an integer representing the i-th operation, which should be set as follows.
- If the i-th operation is Operation +, x_i=-1.
- If the i-th operation is Operation \oplus, x_i should be the integer chosen in that operation.
If there are multiple possible solutions, you may print any of them.
Sample Input 1
3 5 0 3 6 1 4 7 2
Sample Output 1
Yes 4 -1 6 -1 1
The sequence of operations above changes the sequence A as follows.
- Initially: A = (5,0,3,6,1,4,7,2)
- Operation +: A = (6,1,4,7,2,5,0,3)
- Operation \oplus (x = 6)：A = (0,7,2,1,4,3,6,5)
- Operation +: A = (1,0,3,2,5,4,7,6)
- Operation \oplus (x = 1)：A = (0,1,2,3,4,5,6,7)
Sample Input 2
3 2 5 4 3 6 1 0 7
Sample Output 2
No
No sequence of operations achieves the objective.
Sample Input 3
3 0 1 2 3 4 5 6 7
Sample Output 3
Yes 0
Performing zero operations achieves the objective. Whether an empty line is printed or not does not affect the verdict.