← 返回题目列表

AtCoder · pakencamp_2023_day1_k

K. 或设置

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

配点 : 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 。 当
例如,12 \ \mathrm{or} \ 6=14 。 (用二进制表示法, 1100 \ \mathrm{or} \ 0110=1110 )

制約

  • 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