思路与算法

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_i..r_i]$ 精确表示。

输入描述

输入包括多组测试数据。

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

2.每组测试数据：

• 第一行有两个整数 $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$，故答案一定不存在。