配点 : 500 点
問題文
正整数 M 和长度 N 的非负整数序列 给出了 A=(A_1,A_2,\dots ,A_N) 。在这里,0 \leq A_i \leq 2^M-1 有保证。另外,首先 一个整数 X=0 有 X 。
你是 自由重新排列 A 的元素后,执行以下操作。 按照步骤 i=1,2,\ldots,N 操作。
- X \ \mathrm{or} \ A_i \neq 2^M-1 然后, 替换为 X 在 X \ \mathrm{or} \ A_i 。
操作后 X 的数量。
\mathrm{or} 是什么?
整数 a,b 的按位或 a \ \mathrm{or} \ b 定义如下。- a \ \mathrm{or} \ b 以二进制表示法 2^k \ (0 \leq k) 中的位数为a,b 以二进制表示时 2^k 位数 如果存在 1 的东西 1,否则 0 。 当
制約
- 1 \leq N \leq 2\times 10^5
- 1 \le M \le 30
- 0 \le A_i < 2^M
- 输入均为整数。
入力
输入是按以下格式从标准输入给出的。
N M A_1 A_2 \ldots A_N
出力
输出答案。
入力例 1
3 3 4 3 6
出力例 1
2
操作后 X 可以被认为是3,6 的 2 没错。
例如, 对于A=(4,3,6) ,操作如下: 替换为
- X \ \mathrm{or} \ A_1 = 0 \ \mathrm{or} \ 4 = 4 ≠ 2^3-1 所以, 除以X 在 4 。
- X \ \mathrm{or} \ A_2 = 4 \ \mathrm{or} \ 3 = 7 = 2^3-1 因此,请勿执行任何操作。
- X \ \mathrm{or} \ A_3= 4 \ \mathrm{or} \ 6 = 6 ≠ 2^3-1 所以, 除以X 在 6 。
因此,最终 X 的值为 6 。
入力例 2
5 1 1 1 1 1 1
出力例 2
1
入力例 3
8 4 3 5 14 0 10 3 6 12
出力例 3
4