分数: 900 点
问题陈述
一套 X 个非负整数,令 f(X) 表示可以表示为按位的非负整数集合 \mathrm{XOR} 中的两个整数(可能相同) X。举个例子,对于 X=\lbrace 1, 2, 4\rbrace,我们有 f(X)=\lbrace 0, 3, 5, 6\rbrace.
给你一套 N 小于的非负整数 2^M: S=\lbrace A_1, A_2, \dots, A_N\rbrace.
您可以多次执行以下操作。
- 除法 S 分为两套 T_1 和 T_2 (其中之一可能为空)。然后,更换 S 与联盟 f(T_1) 和 f(T_2).
求出需要进行的最少操作次数 S=\lbrace 0\rbrace.
什么是按位 \mathrm{XOR}?
按位 \mathrm{XOR} 非负整数 A 和 B, A \oplus B定义如下。
- 当 A \oplus B 以二进制形式写入, k- 第最低位 (k \geq 0)是 1 如果恰好是其中之一 k- 第最低位 A 和 B is 1,和 0 否则。
一般来说,按位 \mathrm{XOR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k),可以证明与顺序无关 p_1, p_2, p_3, \dots, p_k.
约束
- 1 \leq N \leq 300
- 1 \leq M \leq 300
- 0 \leq A_i < 2^{M}
- A_i\ (1\leq i \leq N) 成对不同。
- 每个 A_i 恰好给出 M 二进制数字(可能带有前导零)。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \vdots A_N
输出
打印答案。
样本输入 1
4 2 00 01 10 11
示例输出 1
2
在第一个操作中,您可以除 S 进入 T_1=\lbrace 0, 1\rbrace, T_2=\lbrace 2, 3\rbrace,其中 f(T_1) =\lbrace 0, 1\rbrace, f(T_2) =\lbrace 0, 1\rbrace,替换 S 与 \lbrace 0, 1\rbrace.
在第二个操作中,您可以除 S 进入 T_1=\lbrace 0\rbrace, T_2=\lbrace 1\rbrace, 制作 S=\lbrace 0\rbrace.
没有办法使 S=\lbrace 0\rbrace 少于两次操作,所以答案是 2.
示例输入 2
1 8 10011011
示例输出 2
1
在第一个操作中,您可以除 S 进入 T_1=\lbrace 155\rbrace, T_2=\lbrace \rbrace, 制作 S=\lbrace 0\rbrace。请注意 T_1 or T_2 可能为空。
示例输入 3
1 2 00
示例输出 3
0
我们有 S=\lbrace 0\rbrace 从头开始;无需任何操作。
示例输入 4
20 20 10011011111101101111 10100111100001111100 10100111100110001111 10011011100011011111 11001000001110011010 10100111111011000101 11110100001001110010 10011011100010111001 11110100001000011010 01010011101011010011 11110100010000111100 01010011101101101111 10011011100010110111 01101111101110001110 00111100000101111010 01010011101111010100 10011011100010110100 01010011110010010011 10100111111111000001 10100111111000010101
示例输出 4
10