← 返回题目列表

AtCoder · agc057_c

C. 增量或异或

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

分数: 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 否则。
例如,我们有 3 \oplus 5 = 6 (以二为基数: 011 \oplus 101 = 110).


你的目标是 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

执行零操作即可达到目标。是否打印空行并不影响判决。