← 返回题目列表

Codeforces · 916/B

B. 杰米和二进制序列(回合后更改)

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

Jamie 正在准备 Codeforces 回合。他对一个问题有了一个想法,但不知道如何解决。帮助他写出以下问题的解决方案:

找到 k 个整数,使每个数字的 2 次方之和等于数字 n,并且答案中最大的整数尽可能小。由于可能有多个答案,因此要求您输出字典顺序最大的一个。

为了更清楚,请考虑长度为 k (a1, a2, ..., ak) 且 $$\sum_{i=1}^{k} 2^{a_i} = n$$ 的所有整数序列。为每个序列指定一个值 $$y = \max_{1 \leq i \leq k} a_i$$ 。在具有最小 y 值的所有序列中,输出字典顺序最大的序列。

有关权力的定义和字典顺序,请参阅注释。

输入

第一行由两个整数 n 和 k (1 ≤ n ≤ 1018, 1 ≤ k ≤ 105) 组成 - 所需的总和以及序列的长度。

输出

如果不存在这样的序列,则在单行中输出“No”(不带引号)。否则,在第一行中输出“Yes”(不带引号),并在第二行中输出用空格分隔的 k 个数字 - 所需的序列。

保证答案序列中的整数符合范围 [ - 1018, 1018]。

示例

输入 #1

23 5

输出 #1

Yes
3 3 2 1 0

输入 #2

13 2

输出 #2

No

输入 #3

1 2

输出 #3

Yes
-1 -1

注意

示例 1:

23 + 23 + 22 + 21 + 20 = 8 + 8 + 4 + 2 + 1 = 23

像 (3, 3, 2, 0, 1) 或 (0, 1, 2, 3, 3) 这样的答案并不是字典顺序最大的。

像 (4, 1, 1, 1, 0) 这样的答案没有最小 y 值。

示例 2:

可以证明不存在长度为2的序列。

示例 3:

$$2^{-1} + 2^{-1} = \frac{1}{2} + \frac{1}{2} = 1$$

2 的幂:

如果 x > 0,则 2x = 2·2·2·...·2(x 次)。

如果 x = 0,则 2x = 1。

如果 x < 0,则 $$2^x = \frac{1}{2^{-x}}$$。

字典顺序:

给定两个相同长度的不同序列 (a1, a2, ... , ak) 和 (b1, b2, ... , bk),对于字典顺序,第一个序列小于第二个序列,当且仅当 ai < bi,对于第一个 i,其中 ai 和 bi 不同。