1000ms

Difficulty: 6

所属公司 : 饿了么

时间 :2025年3月28日(算法方向)

算法与标签>暴力枚举

会员或题库专享

请先，开通会员或购买题库饿了么机考编程题库，可解锁完整内容。

购买饿了么机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（饿了么机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

枚举非空子集：共有 $2^n-1$ 种选择方式，用位掩码从 $1$ 枚举到 $2^n-1$ 。
按位或合并：把每条被选中的 '0'/'1' 字符串看作二进制整数，对所选记录做按位或，得到十进制值 $key$ 。
质数判定：由于 $m\le 14$ ， $key\le 2^{14}-1$ ，用试除法判断 $key$ 是否为质数。
去重：用集合保存所有合法质数，答案为集合大小。

复杂度分析

题目内容

有 $n$ 条开关记录，每条记录是长度为 $m$ 的字符串，仅由字符 '0' 和 '1' 组成。你可以选择至少一条记录，将所选记录按位或，得到一个长度为 $m$ 的二进制串，再把它解释为十进制整数。

统计：所有非空选择方案中，能够得到多少个互不相同的质数。

开关记录条数 $n$ 满足 $1 \le n \le 20$ ，每条记录长度 $m$ 满足 $1 \le m \le 14$ 。

输入描述

第一行包含两个正整数 $n$ 和 $m$ ，分别表示记录条数和每条记录的长度。接下来 $n$ 行，第 $i$ 行包含一个长度为 $m$ 、仅由字符 '0' 和 '1' 组成的字符串 $s_i$ 。