【普及】受限的数组

给你一个大小为 $n$ 的整数数组 $a$ 和一个正整数 $k$。

通过将每个元素 a[i] 替换为 min(nums[i], x)，可以得到一个由值 $x$ 限制的数组。

对于从 $1$ 到 $n$ 的每个整数 $x$，确定是否可以从由 $x$ 限制的数组中选择一个 子序列，使所选元素的和 恰好 为 $k$。

更形式化的描述：

• 请你输出一行包含 $n$ 个数 ans[1], ans[2], ..., ans[n]
• 其中 ans[i] = 1 表示：当 x = i 时，可以选出满足要求的子序列；否则 ans[i] = 0

提示：

• 子序列 是一个从数组中通过删除一些或不删除任何元素（且不改变剩余元素顺序）派生出来的 非空 数组。

输入格式

第一行是一个整数 $T$，代表数据的组数，接下来有 $T$ 组数据

每组数据的第一行 $2$ 个正整数 $n$ 和 $k$

每组数据的第二行包含 $n$ 个正整数表示数组 $a$

输出格式

对于每组数据输出一行，表示 ans[1] 到 ans[n]

2
4 5
4 3 2 4
5 3
1 2 3 4 5

0 0 1 1
1 1 1 1 1

提示

【样例 1 解释】

• 对于 x = 1，限制后的数组为 [1, 1, 1, 1]。可能的和为 1, 2, 3, 4，因此无法选出和为 5 的子序列，输出 0。
• 对于 x = 2，限制后的数组为 [2, 2, 2, 2]。可能的和为 2， 4， 6， 8，因此无法选出和为 5 的子序列，输出 0。
• 对于 x = 3，限制后的数组为 [3, 3, 2, 3]。可以选择子序列 [2, 3]，其和为 5，能选出满足要求的子序列。输出 1。
• 对于 x = 4，限制后的数组为 [4, 3, 2, 4]。可以选择子序列 [3, 2]，其和为 5，能选出满足要求的子序列。输出 1。

【样例 2 解释】

• 对于每个值 x，总是可以从限制后的数组中选择一个子序列，其和正好为 3。所以输出 1 1 1 1 1

【数据范围】

• 对于 $100\%$ 的数据，$1 \leq n, k \leq 4000, 1 \le a_i \le n$
• 单组数据内的 $n$ 之和不超过 $4000$

来源

• leetcode_周赛467_C