题目描述

给定一个编号从 $1$ 到 $100$ 的数组 $a$。初始时，对于 $1 \leq i < 100$ 有 $a_i = 0$，最后一个元素 $a_{100} = 1$。

可以通过增量操作来修改数组 $a$。要执行 $m$ 次增量操作，需要选择 $m$ 个整数 $p_1, p_2, \dots, p_m$（$1 \le p_i < 100$），并按顺序执行赋值操作 $a_{p_i} \leftarrow (a_{p_i} + a_{p_i + 1})$（$i$ 从 $1$ 到 $m$）。

给定一个整数 $n$，找到一组增量操作序列，使得在执行完这些操作后，数组 $a$ 的第一个元素 $a_1$ 等于 $n$。

输入格式

第一行包含两个整数 $t$ 和 $g$（$1 \le t \le 100$，$0 \leq g \leq 5$）——分别表示输入数据的组数和测试块编号。

接下来的 $t$ 行，每行包含一个整数 $n$（$1 \le n \le 10^{18}$）——在执行完增量操作后，$a_1$ 应该达到的目标值。

输出格式

对于每组输入数据，第一行输出一个整数 $m$（$0 \leq m \leq 2000$）——增量操作的次数。

第二行输出 $m$ 个整数 $p_i$（$1 \le p_i < 100$）——增量操作的参数。

如果存在多个正确答案，输出任意一个均可。

1 0
1

99
99 98 ... 7 6 5 4 3 2 1

2 0
3
16

101
99 98 ... 7 6 5 4 3 2 1 1 1
103
99 98 ... 7 6 5 4 4 3 3 2 2 1 1

提示

为了清晰起见，题目描述中的输入样例已被简化。要得到正确答案，请将 $\tt{...}$ 替换为从 $97$ 到 $8$ 的整数序列。

以第二个样例的第二组输入数据为例，其中 $n = 16$。在执行以下操作后，数组 $a$ 的前 $8$ 个元素的变化如下：

• $p_1 = 99$，$a = [0, 0, 0, 0, 0, 0, 0, 0, \ldots, 0, 0, 1, 1]$；
• $p_2 = 98$，$a = [0, 0, 0, 0, 0, 0, 0, 0, \ldots, 0, 1, 1, 1]$；
• $\ldots$
• $p_{93} = 7$，$a = [0, 0, 0, 0, 0, 0, 1, 1, \ldots, 1, 1, 1, 1]$；
• $p_{94} = 6$，$a = [0, 0, 0, 0, 0, 1, 1, 1, \ldots, 1, 1, 1, 1]$；
• $p_{95} = 5$，$a = [0, 0, 0, 0, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]$；
• $p_{96} = 4$，$a = [0, 0, 0, 1, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]$；
• $p_{97} = 4$，$a = [0, 0, 0, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]$；
• $p_{98} = 3$，$a = [0, 0, 2, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]$；
• $p_{99} = 3$，$a = [0, 0, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]$；
• $p_{100} = 2$，$a = [0, 4, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]$；
• $p_{101} = 2$，$a = [0, 8, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]$；
• $p_{102} = 1$，$a = [8, 8, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]$；
• $p_{103} = 1$，$a = [16, 8, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1]$。

评分标准

前四个测试块允许使用不超过 300 次增量操作。

• （$4$ 分）：$n \leq 100$；
• （$6$ 分）：$n = k^2$，其中 $1 \le k \le 100$；
• （$10$ 分）：$n = (2^k - 1)$，其中 $k$ 为整数；
• （$13$ 分）：$n$ 是斐波那契数（即 $n$ 属于序列 $1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$）；
• （最多 $67$ 分）：无额外限制。设使用的增量操作次数为 $c$。如果 $c \le 300$，得 $67$ 分；否则得 $(17 + \left \lfloor \frac{2000 - c}{34} \right \rfloor)$ 分。

用于计算最后一个测试块得分的 $\tt{C++}$ 代码如下：

((c <= 300) ? 67 : (17 + (2000 - c) / 34))

翻译由 DeepSeek V3 完成