← 返回题目列表

AtCoder · ttpc2023_j

J. 套装构造

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

配点 : 100 点

問題文

2 的整数 N 和 还给出了 2 以上 \frac{N(N+1)}{2} 的整数 给出了 M 。非负整数集合 有一个 A 满足以下所有条件,所以我们 1 请构建一个。

  • 0 \in A
  • 2^N - 1 \in A
  • 集合 A 的所有元素 0 以上 2^N - 1 是小于或等于的非负整数(16:08 更正)
  • x, y \in A 如果 x ~ \mathrm{AND} ~ y \in A
  • x, y \in A 如果 x ~ \mathrm{OR} ~ y \in A
  • A 中的元素数量 等于 |A| 是 您也可以写 M 您将获得

T 测试用例,因此请逐一回答。

\mathrm{AND} 是什么? 表示 非負整数 n, m 的按位与 n ~ \mathrm{AND} ~ m 定义如下。 当
  • n ~ \mathrm{AND} ~ m 以二进制表示法 2^k ~ (k \geq 0) 中的位数为 n,m 以二进制表示法 2^k 的两位数字 如果 1 如果 1 ,否则 输出为 0 。
\mathrm{OR} 是什么? 表示 非負整数 n, m 的按位或 n ~ \mathrm{OR} ~ m 定义如下。 当
  • n ~ \mathrm{OR} ~ m 以二进制表示法 2^k ~ (k \geq 0) 中的位数为 n,m 以二进制表示法 2^k 数字中的一个(或两个)是 1 如果 1 ,否则 输出为 0 。

制約

  • 1 \leq T \leq 30
  • 2 \leq N \leq 60
  • 2 \leq M \leq \frac{N(N+1)}{2}
  • 所有输入均为整数

部分点

  • 附加限制 如果正确答案是满足 N \leq 5 的数据集 给出 25 点。 如果您正确回答了所有满足

入力

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

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

\text{case}_i\ (1 \leq i \leq T) 是 您也可以写 i 个测试用例。每个测试用例均按以下格式给出。

N M

出力

T 行。

i 行目 (1 \leq i \leq T) 有i 个测试用例中,一组满足问题陈述的所有条件的非负整数。 A ,不同 M 元素 按以下格式输出为 x_1, x_2, \dots, x_M 。

x_1 x_2 \cdots x_M

x_1, x_2, \dots, x_M 不必按升序排列。

可以证明在这个约束下答案总是存在的。 在第


入力例 1

3
3 5
4 8
60 2

出力例 1

0 1 3 5 7
0 1 3 7 8 9 11 15
0 1152921504606846975

1 个测试用例中, A = \{0, 1, 3, 5, 7\} 满足问题陈述中的所有条件。例如,3 ~ \mathrm{AND} ~ 5 = 1 \in A 、 3 ~ \mathrm{OR} ~ 5 = 7 \in A 。 对于

满足条件 A 没问题,下面的输出也可以接受。要输出的元素不必按升序排列。

7 1 4 0 5

不允许以下输出: 因为 0 \not \in A 。

1 2 3 5 7

不允许以下输出: 因为 3, 5 \in A 同时 3 ~ \mathrm{AND} ~ 5 = 1 \not \in A 。

0 3 4 5 7

也不允许以下输出:请注意,集合不是多重集合。 请注意,在第

7 7 7 0 0

3 个测试用例中,输出可能不适合 32 位整数类型。另请注意,输入/输出示例不满足部分点约束。 有