← 返回题目列表

Codeforces · 2028/F

F. 爱丽丝的额外冒险

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

请注意,内存限制不正常。

柴郡猫给爱丽丝出了一个谜语:给定 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ 和目标 $$$m$$$,有没有办法将 $$$+$$$ 和 $$$\times$$$ 插入到表达式 $$$$$$a_1 \circ a_2 \circ \cdots \circ 的圆圈中a_n = m$$$$$$ 使其成立吗?我们遵循通常的操作顺序:$$$\times$$$ 在 $$$+$$$ 之前完成。

虽然爱丽丝非常擅长国际象棋,但她不擅长数学。请帮助她,让她找到离开仙境的出路!

输入

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

每个测试用例的第一行包含两个整数 $$$n, m$$$ ($$$1\le n\le 2\cdot 10^5$$$; $$$1\le m\le 10^4$$$) - 分别是整数的数量和目标。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0\le a_i\le 10^4$$$) — 数组 $$$a$$$ 的元素。

所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,如果可以通过插入 $$$+$$$ 或 $$$\times$$$ 来获取目标,则输出不带引号的“YES”,否则输出“NO”。

您可以在任何情况下输出每个字母(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

6
5 4
2 1 1 1 2
5 5
2 1 1 1 2
5 6
2 1 1 1 2
5 7
2 1 1 1 2
5 8
2 1 1 1 2
5 6
2 0 2 2 3

输出 #1

YES
YES
YES
YES
NO
YES

注意

前四个测试用例的可能解决方案如下所示。 $$$$$$\begin{align*} 2 \times 1 + 1 \times 1 \times 2 &= 4 \\ 2 \times 1 + 1 + 1 \times 2 &= 5 \\ 2 \times 1 + 1 + 1 + 2 &= 6 \\ 2 + 1 + 1 + 1 + 2 &= 7 \\ \end{align*}$$$$$$在第五个测试用例中不可能得到 $$$8$$$ 的结果。