#1947. strings
strings
strings
题目描述
标题: strings - Problem - QOJ.ac
The problem was used in the following contests:
小 p 参加政治考试,总共有 n 道判断题。一些题目小 p 可以靠自己的能力蒙一个答案,然而对于一些他完全不会的题,他会通过某种方式得到标准答案然后填上去。小p具有时间倒流的能力,因此可以参加 q 次同样的考试,不过每次考试他的策略未必相同。众所周知,只有 AK 才能满足小 p 的欲望,而每道题的答案是未知的,小 p 想知道有多少种标准答案使得他在至少一次考试中能 AK。
输入格式
第一行两个整数 n,q。
下接q行,每行一个长为n的字符串,包含0 、1 、? 这三种字符,数字意味着答案是小p蒙的(可以匹配这种字符),? 表示这道题他得到了标准答案(可以匹配任意字符)。
输出格式
一行一个整数,表示有多少长为 n 的 0/1 串 s,使得 s 满足 q 个串中至少一个串的形式。
样例一
input
4 2
??01
1??1
output
6
explanation
共有这些合法的串:0001, 0101, 1001, 1101, 1011, 1111
限制与约定
子任务n≤q≤特殊性质分值 120203 2302012 3253011 430306 530100问号总数≤4011 6305016 73010041
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 2
??01
1??1
6