/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
非負整数からなる集合 X に対し、X に属する 2 つの整数（同じ整数でもよい）のビット単位 \mathrm{XOR} として表せるような非負整数からなる集合を f(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 を 2 つの集合 T_1, T_2 に分ける（ T_1, T_2 のいずれかが空集合になってもよい）。その後、 S を f(T_1), f(T_2) の和集合で置き換える。
S を \lbrace 0\rbrace にするのに必要な最小の操作回数を求めてください。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\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 は 2 進表記でちょうど M 桁で与えられる（ A_i が M 桁より少ない場合、 leading zero をつけて与えられる）
- 与えられる入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \vdots A_N
出力
答えを出力せよ。
入力例 1
4 2 00 01 10 11
出力例 1
2
1 回目の操作では 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 に置き換わります。
2 回目の操作で T_1=\lbrace 0\rbrace, T_2=\lbrace 1\rbrace と分けると S=\lbrace 0\rbrace となります。
2 回未満の操作で S を \lbrace 0\rbrace にすることはできないので答えは 2 となります。
入力例 2
1 8 10011011
出力例 2
1
1 回目の操作で T_1=\lbrace 155\rbrace, T_2=\lbrace \rbrace と分けると S は \lbrace 0\rbrace になります。操作の際は T_1, 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
Score : 900 points
Problem Statement
For a set X of non-negative integers, let f(X) denote the set of non-negative integers that can be represented as the bitwise \mathrm{XOR} of two integers (possibly the same) in X. As an example, for X=\lbrace 1, 2, 4\rbrace, we have f(X)=\lbrace 0, 3, 5, 6\rbrace.
You are given a set of N non-negative integers less than 2^M: S=\lbrace A_1, A_2, \dots, A_N\rbrace.
You may perform the following operation any number of times.
- Divide S into two sets T_1 and T_2 (one of them may be empty). Then, replace S with the union of f(T_1) and f(T_2).
Find the minimum number of operations needed to make S=\lbrace 0\rbrace.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows.
- When A \oplus B is written in binary, the k-th lowest bit (k \geq 0) is 1 if exactly one of the k-th lowest bits of A and B is 1, and 0 otherwise.
Generally, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), which can be proved to be independent of the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1 \leq N \leq 300
- 1 \leq M \leq 300
- 0 \leq A_i < 2^{M}
- A_i\ (1\leq i \leq N) are pairwise distinct.
- Each A_i is given with exactly M digits in binary (possibly with leading zeros).
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \vdots A_N
Output
Print the answer.
Sample Input 1
4 2 00 01 10 11
Sample Output 1
2
In the first operation, you can divide S into T_1=\lbrace 0, 1\rbrace, T_2=\lbrace 2, 3\rbrace, for which f(T_1) =\lbrace 0, 1\rbrace, f(T_2) =\lbrace 0, 1\rbrace, replacing S with \lbrace 0, 1\rbrace.
In the second operation, you can divide S into T_1=\lbrace 0\rbrace, T_2=\lbrace 1\rbrace, making S=\lbrace 0\rbrace.
There is no way to make S=\lbrace 0\rbrace in fewer than two operations, so the answer is 2.
Sample Input 2
1 8 10011011
Sample Output 2
1
In the first operation, you can divide S into T_1=\lbrace 155\rbrace, T_2=\lbrace \rbrace, making S=\lbrace 0\rbrace. Note that T_1 or T_2 may be empty.
Sample Input 3
1 2 00
Sample Output 3
0
We have S=\lbrace 0\rbrace from the beginning; no operation is needed.
Sample Input 4
20 20 10011011111101101111 10100111100001111100 10100111100110001111 10011011100011011111 11001000001110011010 10100111111011000101 11110100001001110010 10011011100010111001 11110100001000011010 01010011101011010011 11110100010000111100 01010011101101101111 10011011100010110111 01101111101110001110 00111100000101111010 01010011101111010100 10011011100010110100 01010011110010010011 10100111111111000001 10100111111000010101
Sample Output 4
10