← 返回题目列表

AtCoder · jsc2022_final_d

D. 并且是 0

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

配点 : 800 点

問題文

整数 N 。

非負整数列 A=(A_1,A_2,\cdots,A_k) ,请判断是否有满足以下条件的。 另外,如果有的话,请给我看一张。

  • A 长度 k 是 仅由 1 以上 100 以下。
  • A 的每个元素是 它是小于或等于 0 以上 2^{20}-1 的整数。
  • A 的非空(不一定连续)子序列,其值为按位 考虑变成 \mathrm{AND} 是 0 的东西。 这样的子序列的数量正好是 N 。 然而,这里,提取位置不同。 2 即使两个子序列具有相同的值,它们也会被视为不同。
位单位 \mathrm{AND} 什么是操作?

整数 A, B 按位 \mathrm{AND}、A\ \mathrm{AND}\ B 定义如下。

  • A\ \mathrm{AND}\ B 以二进制表示法 2^k (k \geq 0) 的位数是A, B 以二进制表示法 2^k 的两位数字 如果 1 如果 1,否则 0 。
例如,3\ \mathrm{AND}\ 5 = 1 (二进制表示法: 011\ \mathrm{AND}\ 101 = 001)。
一般 k 整数 p_1, p_2, p_3, \dots, p_k 按位 \mathrm{AND} 是 仅由 (\dots ((p_1\ \mathrm{AND}\ p_2)\ \mathrm{AND}\ p_3)\ \mathrm{AND}\ \dots\ \mathrm{AND}\ p_k) ,即 可以证明 p_1, p_2, p_3, \dots p_k 不依赖于顺序。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 所有输入值均为整数

入力

输入是按以下格式从标准输入给出的。

N

出力

满足条件的序列 如果 A 不存在, 输出-1 。 如果存在,则按照以下格式输出。

k
A_1 A_2 \cdots A_k

如果有多个解满足条件,则任何一个输出都将被视为正确答案。


入力例 1

3

出力例 1

3
2 1 1

A 的非空子序列,其值按位 \mathrm{AND} 是 0 如下 3 有两个。

  • (2,1) (1,2 第一个元素被提取)
  • (2,1) (1,3 第一个元素被提取)
  • (2,1,1) (1,2,3 第一个元素被提取)