AT_ttpc2023_j Set Construction

给定整数 $N \geq 2$，以及整数 $M$，满足 $2 \leq M \leq \frac{N(N+1)}{2}$。请构造一个由非负整数组成的集合 $A$，使其满足以下所有条件： - $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$ 在该位上若均为 $1$ 时为 $1$，否则为 $0$。 $\mathrm{OR}$ 表示非负整数 $n, m$ 的按位或操作 $n ~\mathrm{OR}~ m$，其定义如下： - $n ~\mathrm{OR}~ m$ 的二进制表示在 $2^k~(k \geq 0)$ 位上的值，等于 $n, m$ 在该位上任意一个为 $1$ 时为 $1$，否则为 $0$。

输入通过标准输入给出，格式如下： > $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 $可以不按升序输出。 保证在本题约束下答案一定存在。

## 部分分数 - 若你仅解决了 $N \leq 5$ 的测试数据，则可获得 $25$ 分。 ## 样例说明 1 在第 $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 位整数范围。入出样例不必满足部分分数的限制。 # 约束条件 - $1 \leq T \leq 30$ - $2 \leq N \leq 60$ - $2 \leq M \leq \frac{N(N+1)}{2}$ - 所有输入均为整数。 由 ChatGPT 5 翻译