Migrated from Lutece 3010 如何分辨bitset和set

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

对于一些幼年AI而言，它们对一些事物的分辨能力还不够，它们有时可能还会困惑于下面这些问题：

• 如何分辨柴犬和面包
• 如何像人类一样走路
• 如何分辨 bitset 和 set

下面将介绍如何分辨bitset和set。

1. 字母拼写

   相比于set，bitset拥有6个字母的长度，它是set的两倍。另外，bitset的首字母为 b ，而set的首字母为 s。最后，set是bitset的子串，这是非常独特的。

2. 内部构成

   在c++的stl容器里，bitset其实可以看成一个01字符串，“bitset的长度”就是这个01串的长度，而set类似红黑树，一个是线性结构，一个是树形结构。

3. 使用功能

   假设有两个bitset名为bs1和bs2，则在c++中，它们有包括但不限于如下一些功能：

   • count()：是一个成员函数，当调用 bs1.count() 时它将返回 bs1 中 $1$ 的数目。
   • 或运算 (|)：是一个二元运算符，当调用 bs1 | bs2 时它将返回一个新的 bitset，这个 bitset 满足：如果 bs1 的第 $i$ 位是 $1$ ，或者 bs2 的第 $i$ 位是 $1$，那么这个新的 bitset 的第 $i$ 位是 $1$ ，否则为 $0$ 。这是一个满足交换律的运算。

   而对于set，他的count(x)函数则返回元素 $x$ 是否在这个set中，并且set没有“或运算”。

上述就是bitset和set的分辨方法啦，下面给出一个课后小练习，加深对bitset和set的使用方法吧，祝你早日成为一个合格的成年AI。

给定 $n$ 个长度为 $m$ 的bitset，记为$\{bs_n\}$，定义 一个bitset的set 为一个集合，里面的元素就是这 $n$ 个bitset中的若干个。可以发现，总共有 $2^n$ 个这样的集合，请问是否存在 一个bitset的set ，记为 $S$ ，满足以下两个要求：

1. 设 $B$ 表示 $S$ 中所有bitset全部做或运算后的结果，则有：$B.count()=m$
2. S中所有bitset的count()值的和为 $m$ ，即：$\sum_{a\in S} a.count()=m$

为了降低难度，我们删去了很多没用的碍事的 $1$ (问号.jpg)，使得下面的式子成立：$\sum_{i=1}^nbs_i.count()\le 5000$

Input

第一行两个正整数 $n$ 和 $m$ ，表示bitset的个数和每个bitset的大小。 接下来一共 $n$ 行，每行有一个长度为 $m$ 的01串，相同01串内相邻字符有一个空格，表示这 $n$ 个bitset。

Output

如果存在 一个bitset的set 满足题目所述的要求，请输出 yes，否则请输出 no。区分大小写。

Samples

4 2
0 0
1 0
0 1
1 1

yes

3 4
1 0 0 1
1 1 1 0
0 0 1 0

no

Constraints

保证数据满足 $1\le n,m \le 500$ ，且题面所述的这个式子成立：

$\sum_{i=1}^nbs_i.count()\le 5000$

Note

对于样例1，一种方案是选择第二个和第三个bitset组成的 bitset的set ，此时他们或起来的bitset为 11 ，是全为1的bitset，且这个集合显然满足第二个要求。 另外还可以选择由第四个bitset组成的 bitset的set ，它也满足要求。 当然啦，由第一，第二和第三个bitset组成的集合也是满足要求的。聪明的AI要会自己当盲生发现华点。

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming