题解

题面描述

题目给定了$n$个密匙片段，每个片段均为长度为$m$的二进制字符串（仅含字符$'0'$和$'1'$）。要求从这$n$个片段中任意选择若干（至少一个），将选择的片段进行按位或运算，得到一个二进制数。把这个二进制数转换为十进制后，只有当其正好为质数时才被视为一个合法的密钥。要求统计所有能够构造出的不同质数密钥的个数。

思路

题目内容

我们截获了$n$条片段，每一个片段均由$m$个字符组成，字符为‘$0$’或者‘$1$’。

你可以选择一些片段，将它们做按位或运算后，生成一个完整的密钥。根据加密算法的需求，合成后的密钥在转换为十进制的数值后必须

恰好为一个质数，才能符合安全系统的运算要求(质数在许多公钥密码体系中具有特殊意义)。

请你设计一个程序，帮助安全专家确定:任意选取片段，能得到多少个不同的质数密钥?

输入描述

第一行输入两个正整$数n,m(1≦n≦20;1≦m≦14)$代表片段数量、片段长度。

此后$n$行，第$i$行输入一个长度为$m$，仅由字符‘$0$’和‘$1$’组成的字符串 $S_i$表示第$i$个片段。

输出描述

输出一个整数，代表能得到的质数密钥的数量。

样例1

输入

3 4
0010
1000
1010

输出

1

说明

在这个样例中，选择第一条密匙片段，$(0010)_2$，是一个质数。我们可以证明，这是唯一一种能得到质数密匙的选取方案。

样例2

输入

3 3
100
001
110

输出

2

说明

在这个样例中，一共有两种选取方案，分别是：

• 选择第一条和第二条密匙片段，$(100)_2xor(001)_2$$=(101)_2=5$，是一个质数。
• 选择第二条和第三条密匙片段，$(001)_2xor(110)_2$$=(111)_2=7$，也是一个质数。

样例3

输入

2 4
1000
0000

输出

0