← 返回题目列表

AtCoder · arc155_e

E. 分割和方形

中文机器翻译题面 查看原题

分数: 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 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).
一般来说,按位 \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