思路与算法

1）预处理所有候选区间

• 将每个 $a_i$ 转为二进制串 $b_i$（如 $2\to "10"$）。
• 在 $s$ 中扫描所有长度为 $|b_i|$ 的窗口，记录与 $b_i$ 完全相同的出现位置 $(l,r)$（下标从 1 开始，$r=l+|b_i|-1$）。
• 若某个 $i$ 完全没有匹配位置，则本组直接输出 NO。

2）位压 DP（按右端点递增选区间）

题目内容

小钟有一个长度为$n$的$01$串$s$，即仅由字符$0$和$1$组成的字符串，如$0101101$。除此之外他还有$m$个数字，分别用$a_1,a_2,..a_m$表示。

小钟很好奇，他能否选择$m$个不相交的区间$[l_1,r_1][l_2,r_2],...,[l_m,r_m]$，使得对于任意的$a_i$,其二进制表示(没有前导$0$，$0$的二进制表示就是$0$)，都能用$s$的某个连续子串$s_{l_j,l_{j}+1,...r_j}$来表示。

输入描述

输入包括多组测试数据。

输入第一行包括一个正整数$T(1≤T≤20)$,表示测试数据的组数。

每组测试数据的第一行有两个整数$n(1≤n≤100),m(1≤m≤6)$，分别表示$01$串$s$的长度，数字个数。

第二行有一行长度为$n$的$01$串$s$。

第三行有$m$个整数$a_1,a_2,...a_m(0≤a_i<2^{10})$,表示小钟的$m$个数字。

输出描述

对于每组测试数据，如果存在答案，输出一行“$YES$”;否则，输出一行“$NO$”。

样例1

输入

2
5 2
10110
2 1
5 1
00000
1

输出

YES
NO

说明

对于第一组测试数据，$2$的二进制表示为$10$，$1$的二进制表示为$1$，其中一种可以选择的区间 为 $[1,2]、[3,3]$。

对于第二组测试数据，$1$的二进制表示为$1$，由于$01$串中不存在字符$1$，故答案一定不存在。