← 返回题目列表

AtCoder · arc182_b

B. |{地板(A_i/2^k)}|

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

分数: 500 点

问题陈述

给你正整数 N 和 K.

长度的整数序列 N 其中所有元素都位于 1 和 2^K - 1,包含在内,被称为 好的序列.

的 分数 本实验的 一个好的序列 A=(A_1,A_2,\ldots,A_N) 定义如下:

  • 不同整数的数量可以表示为 \displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor 使用整数 i 之间 1 和 N,包含在内,并且是一个非负整数 k.

例如,对于 A=(3,5),五个整数可以表示为 \displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor: 0, 1, 2, 3,和 5,所以分数是 5.

找到一个得分最高的好序列。

对于每个输入文件,您都会得到 T 测试用例解决。

约束

  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 10^5
  • 1 \leq K \leq 30
  • 总和 N 单个输入文件中的测试用例最多 2 \times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出。在这里, \text{case}_i 表示 i- 第一个测试用例。

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

每个测试用例均按以下格式给出:

N K

输出

打印 T 行。

的 i- 第行应包含以下内容的答案 \mathrm{case}_i.

如果有多个得分最高的好序列,则其中任何一个都将被接受。


示例输入 1

3
3 3
7 2
8 20

示例输出 1

5 6 7
2 2 3 3 1 3 3
662933 967505 876482 840117 1035841 651549 543175 781219

考虑第一个测试用例。

对于 A=(5,6,7),七个整数可以表示为 \displaystyle \left\lfloor\frac{A_i}{2^k} \right\rfloor: 0, 1, 2, 3, 5, 6,和 7,所以它的分数是 7.

输出如 A=(7,4,5) 和 A=(6,5,4) 也将被接受。