配点 : 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 位整数类型。另请注意,输入/输出示例不满足部分点约束。 有