#PQJ2398x13625. QOJ 2398_13625

    ID: 2813 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2019 集训动态规划

QOJ 2398_13625

标题: strings - Problem - QOJ.ac

Statistics

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