分数: 1100 点
问题陈述
给你一个正整数 N 和一个序列 A = (A_0, A_1, \ldots, A_{2^N-1}) of 2^N 条款,其中每个 A_i 是介于 0 和 2^N-1 (含)和 A_i\neq A_j 成立,如果 i\neq j.
您可以对以下两种操作 A:
- 操作 +:对于每个 i,更改 A_i to (A_i + 1) \bmod 2^N.
- 操作 \oplus: 选择一个整数 x 之间 0 和 2^N-1。对于每一个 i,更改 A_i to A_i\oplus x.
在这里, \oplus 表示按位 \mathrm{XOR}.
什么是按位 \mathrm{XOR}?
按位 \mathrm{XOR} 非负整数 A 和 B, A \oplus B,定义如下:
- 当 A \oplus B 以基数 2 书写,即 2^k的地点 (k \geq 0)是 1 如果恰好是其中之一 A 和 B is 1,和 0 否则。
你的目标是 A_i = i 对于每个 i。确定是否可以实现。可以证明,在该问题的约束下,最多可以达到目标 10^6 操作(如果可以实现的话)。打印这样一个操作序列。
约束
- 1\leq N\leq 18
- 0\leq A_i \leq 2^N - 1
- A_i\neq A_j,如果 i\neq j
输入
输入由标准输入按以下格式给出:
N
A_0 A_1 \ldots A_{2^N - 1}
输出
如果可以的话 A_i = 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 应该是该操作中选择的整数。
如果有多种可能的解决方案,您可以打印其中任何一个。
示例输入 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
执行零操作即可达到目标。是否打印空行并不影响判决。