利用一个叫做 FleaSeek 的大语言模型,跳蚤王国治下的一家技术公司开发了 $m$ 个性格各异的 bot,然后把它们接入了网络。
为了向跳蚤宇宙的成功表示祝贺,伏特跳蚤国王决定使用这些 bot 对跳蚤宇宙的 $n$ 个帖子进行自动评论。
其中第 $i$ 个 bot 有一个固定的参数 $\text{len}_i$。在使用第 $i$ 个 bot 之前,伏特需要选择一个时间戳 $t_i\in[1,n-\text{len}_i+1]$,然后这个 bot 就会自动检索发表顺序第 $[t_i,t_i+\text{len}_i-1]$ 名范围内的所有帖子,根据自己的语料库,结合联网搜索,分别追加一条自动评论。
现在有一个序列 $a_1\sim a_n$,表示我们希望在发表顺序第 $i$ 名的帖子下面追加 $a_i$ 条自动评论。
你需要对于 $\{1,2,\cdots,m\}$ 的每个子集,判断是否存在一种方法,使用这个子集中的每个 bot 各恰好一次,并且给每个 bot 选择合适的时间戳 $t_i$,使得这些 bot 执行后追加的评论数量恰好与 $a_1, a_2, \cdots, a_n$ 相符合。
输入格式
第一行包含两个正整数 $n$ 和 $m$,表示帖子序列的长度和 bot 的数量。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$,其中第 $i$ 个整数表示帖子 $i$ 下需要追加的评论数。
第三行包含 $m$ 个整数 $\text{len}_1, \text{len}_2, \dots, \text{len}_m$,其中第 $i$ 个整数表示第 $i$ 个 bot 的参数 $\text{len}_i$。
输出格式
输出一个长度为 $2^m$ 的字符串,其中第 $i$ 个字符表示当将 $i-1$ 转换为二进制形式 $\sum_{j=1}^{m} c_j 2^{j-1} (0 \leq c_j \leq 1)$ 时,若选择的 bot 子集 $\{x | c_x = 1\}$ 可以找到合法的操作方案,则输出字符 1
,否则输出字符 0
。
样例一
input
3 4 1 2 1 1 2 2 3
output
0000001001000000
explanation
只有 $\{2,3\},\{1,4\}$ 满足条件。
样例二
input
5 5 1 2 2 2 1 1 2 3 4 5
output
00000000000001000001100000000000
样例三~八
他们分别满足 $2,3,4,5,6,7$ 的限制。
限制与约定
对于所有数据,保证 $1\leq n\leq10^5$,$1\leq m\leq17$,$0\leq a_i\leq m$,$1\leq\text{len}_i\leq n$。
子任务编号 | 子任务分值 | $n\leq$ | $m\leq$ | 特殊性质 |
---|---|---|---|---|
$1$ | $10$ | $10$ | $5$ | 无 |
$2$ | $20$ | $10^5$ | $10$ | 无 |
$3$ | $10$ | $10^5$ | $12$ | 无 |
$4$ | $10$ | $10^5$ | $14$ | 无 |
$5$ | $15$ | $10^5$ | $16$ | 无 |
$6$ | $10$ | $10^5$ | $17$ | 保证所有 $a_i$ 相同 |
$7$ | $25$ | $10^5$ | $17$ | 无 |
时间限制:$\texttt{3.5s}$
空间限制:$\texttt{1GB}$