← 返回题目列表

AtCoder · typical90_cb

080. 分享比特(★6)

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

配点: 6 点

問題文

N 个非负整数 A_1,A_2,\ldots,A_N 。

0 以上 2^D 的整数 x , 选择最大化i=1,2,\ldots,N 请找出有多少个满足以下条件的情况。

  • A_i 和 按字典顺序比较 x 的按位与(按位逻辑与)\operatorname{AND})不是 0 。
关于按位与(按位逻辑与\operatorname{AND})

非負整数 A,B 的按位与(按位逻辑与)\operatorname{AND})、A\ \operatorname{AND}\ B 定义如下。

  • A\ \operatorname{AND}\ B 以二进制表示法 2^k\ (k\geq0) 中的位数为A,B 以二进制表示法 2^k 的两位数字 如果 1 如果 1,否则 输出为 0 。
例如,3\ \operatorname{AND}\ 5=1 (二进制表示法: 011\ \operatorname{AND}\ 101=001)。

制約

  • 1\leq N\leq20
  • 0\leq D\leq60
  • 0\leq A_i<2^D\ (1\leq i\leq N)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N D
A_1 A_2 \cdots A_N

出力

N 满足所有条件的整数 x 的编号。


入力例 1

4 3
1 3 4 5

出力例 1

2

0 以上 2^3 的整数 x 分别满足以下条件。

  • 0 不满足任何条件。
  • 1 是 您也可以写 1,2,4 满足第一个条件,但3 不满足第二个条件。
  • 2 是 您也可以写 2 满足第一个条件,但1,3,4 不满足第二个条件。
  • 3 是 您也可以写 1,2,4 满足第一个条件,但3 不满足第二个条件。
  • 4 是 您也可以写 3,4 满足第一个条件,但1,2 不满足第二个条件。
  • 5 满足所有条件。
  • 6 是 您也可以写 2,3,4 满足第一个条件,但1 不满足第二个条件。
  • 7 满足所有条件。

因此,答案是 2 。


入力例 2

5 21
1050624 32772 493952 144 869120

出力例 2

869120

入力例 3

20 60
216181578206878016 81348488767472704 26388280246272 281543729742896 72127981178847488 2199108462600 585610888171487234 22027813536776 567459673280576 146648462866649600 144484898860704776 576471786208755714 4398621196432 144141576657960976 81069330992726040 360851057582278674 17859112 11570646360064 144115206396936193 1702052723957760

出力例 3

977902973481140224

输入或输出的值 32 可能无法容纳在位整数中。