← 返回题目列表

Codeforces · 2114/G

G. 构建一个数组

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

昨天,Dima 发现了一个空数组,并决定向其中添加一些整数。他可以无限次执行以下操作:

  • 将任意整数添加到数组的左端或右端。
  • 那么,只要数组中存在一对相同的相邻元素,就会用它们的和来替换它们。

可以证明,数组中最多同时存在一对这样的对。

例如,如果数组是$$$[3, 6, 4]$$$,我们在左边添加数字$$$3$$$,那么数组首先会变成$$$[3, 3, 6, 4]$$$,然后前两个元素会被$$$6$$$替换,数组就会变成$$$[6, 6, 4]$$$,然后—— $$$[12, 4]$$$。

执行操作后 正是 $$$k$$$次,他认为自己获得了长度为$$$n$$$的数组$$$a$$$,但他不记得自己应用了哪些操作。确定是否存在可以从空数组生成给定数组 $$$a$$$ 的 $$$k$$$ 操作序列,或者确定这是不可能的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例描述的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$n \le k \le 10^6$$$) — 结果数组的长度和操作数。

第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 10^9, a_{i - 1} \ne a_i$$$) — 结果数组的元素。

保证所有测试用例的 $$$n$$$ 值的总和不超过 $$$10^5$$$。

输出

对于每个测试用例,如果没有合适的长度为$$$k$$$的操作序列,则输出“NO“。否则,输出“是".

您可以输出“是“和”NO" 在任何情况下(例如,字符串 "是", "是的", "是“,和”是“将被识别为肯定答案)。

示例

输入
复制

8
3 3
2 1 4
3 7
2 1 4
2 15
2 16
3 10
256 32 1
3 289
768 96 1
3 290
768 96 1
5 7
5 1 6 3 10
4 6
6 8 5 10

输出
复制

YES
NO
YES
YES
YES
NO
YES
YES