【集训队作业2018】strings - 题目

小p参加政治考试，总共有 $n$ 道判断题。一些题目小p可以靠自己的能力蒙一个答案，然而对于一些他完全不会的题，他会通过某种方式得到标准答案然后填上去。小p具有时间倒流的能力，因此可以参加 $q$ 次同样的考试，不过每次考试他的策略未必相同。众所周知，只有AK才能满足小p的欲望，而每道题的答案是未知的，小p想知道有多少种标准答案使得他在至少一次考试中能AK。

输入格式

第一行两个整数 $n, q$ 。

下接 $q$ 行，每行一个长为 $n$ 的字符串，包含0 、1 、? 这三种字符，数字意味着答案是小p蒙的（可以匹配这种字符）， $?$ 表示这道题他得到了标准答案（可以匹配任意字符）。

输出格式

一行一个整数，表示有多少长为 $n$ 的 $01$ 串 $s$ ，使得 $s$ 满足 $q$ 个串中至少一个串的形式。

样例一

input

4 2
??01
1??1

output

explanation

共有这些合法的串：0001, 0101, 1001, 1101, 1011, 1111

限制与约定

子任务	$n \leq$	$q \leq$	特殊性质	分值
1	$20$	$20$		$3$
2	$30$	$20$		$12$
3	$25$	$30$		$11$
4	$30$	$30$		$6$
5	$30$	$100$	问号总数 $\leq 40$	$11$
6	$30$	$50$		$16$
7	$30$	$100$		$41$

时间限制： $1s$

空间限制： $512MB$

下载

样例数据下载

Universal Online Judge

UOJ

#425. 【集训队作业2018】strings